# Comb Sort

# Comb Sort

Comb sort improves bubble sort by comparing elements that are far apart before comparing adjacent elements. It starts with a large gap and repeatedly shrinks that gap until it reaches 1.

The main idea is to remove small elements near the end and large elements near the beginning earlier than bubble sort would.

## Problem

Given a sequence $A$ of length $n$, reorder it such that

$$
A[0] \le A[1] \le \cdots \le A[n-1]
$$

## Algorithm

Start with gap $n$. Divide the gap by a shrink factor, commonly about $1.3$, until the gap becomes 1. Keep scanning while swaps still occur.

```id="k5x8p2"
comb_sort(A):
    n = length(A)
    gap = n
    shrink = 1.3
    sorted = false

    while sorted == false:
        gap = floor(gap / shrink)
        if gap <= 1:
            gap = 1
            sorted = true

        i = 0
        while i + gap < n:
            if A[i] > A[i + gap]:
                swap(A[i], A[i + gap])
                sorted = false
            i = i + 1
```

## Example

Let

$$
A = [8, 4, 1, 56, 3, 44, 23, 6]
$$

Early passes use large gaps, so values can move long distances:

| gap | effect                             |
| --- | ---------------------------------- |
| 6   | compares far-apart elements        |
| 4   | moves misplaced elements closer    |
| 3   | reduces medium-distance inversions |
| 2   | nearly orders the array            |
| 1   | finishes like bubble sort          |

Final result:

$$
[1, 3, 4, 6, 8, 23, 44, 56]
$$

## Correctness

Comb sort repeatedly swaps out-of-order pairs at decreasing gaps. When the gap becomes 1, the algorithm performs adjacent comparisons like bubble sort. It continues until a full gap-1 pass completes without swaps, which means every adjacent pair is ordered. Therefore the entire sequence is sorted.

## Complexity

| case    | time                          |
| ------- | ----------------------------- |
| best    | $O(n \log n)$                 |
| worst   | $O(n^2)$                      |
| average | often better than bubble sort |

Space complexity:

$$
O(1)
$$

## Properties

* in-place
* not stable
* simple gap-based improvement over bubble sort
* depends on shrink factor

## When to Use

Comb sort is useful as a simple improvement over bubble sort when implementation must remain small. It is mainly educational, but it shows how gap-based comparisons can remove long-distance inversions before the final adjacent pass.

## Implementation

```id="m9q2x4"
def comb_sort(a):
    n = len(a)
    gap = n
    shrink = 1.3
    sorted_flag = False

    while not sorted_flag:
        gap = int(gap / shrink)
        if gap <= 1:
            gap = 1
            sorted_flag = True

        i = 0
        while i + gap < n:
            if a[i] > a[i + gap]:
                a[i], a[i + gap] = a[i + gap], a[i]
                sorted_flag = False
            i += 1

    return a
```

```id="z4k7v1"
func CombSort[T constraints.Ordered](a []T) {
    n := len(a)
    gap := n
    shrink := 1.3
    sorted := false

    for !sorted {
        gap = int(float64(gap) / shrink)
        if gap <= 1 {
            gap = 1
            sorted = true
        }

        for i := 0; i+gap < n; i++ {
            if a[i] > a[i+gap] {
                a[i], a[i+gap] = a[i+gap], a[i]
                sorted = false
            }
        }
    }
}
```