Comb Sort

Bubble sort with a gap that starts large and shrinks by ~1.3× each pass, letting small values near the end move far in one step.

Category

Sorting

Time complexity

O(n²/2ᵖ) (p is the number of gap-shrink iterations, from the algorithm's original analysis — an unusual notation, but a legitimate one. Comb sort's average case is not rigorously proven in general; this is the commonly cited approximation.)

Space complexity

O(1)

Pseudocode

gap ← n
shrink gap by 1.3 each pass
compare a[i], a[i+gap]
swap if out of order
done when gap 1 and no swaps

Reference implementation

gap = n
while gap > 1 or swapped:
    gap = max(1, int(gap / 1.3))
    for i in range(n - gap):
        if a[i] > a[i+gap]: swap

Open the interactive Comb Sort visualisation →