Comb Sort

What is comb sort?

Comb sort is bubble sort with a gap. Bubble sort only compares neighbors. Comb sort first compares values that are far apart, swaps them if they are out of order, and then makes the gap smaller each pass. The last passes use a gap of 1, which is plain bubble sort, but by then the list is almost sorted.

The big gaps fix the worst problem of bubble sort: small values stuck near the end (often called turtles). A gap of 6 lets a small value jump 6 places in one swap instead of 1.

How it works, step by step

Press play above. Blue bars are being compared, orange bars are being swapped. Early on, the two blue bars are far apart. Watch them get closer pass by pass.

1. Start with the gap g equal to the length of the list.
2. Shrink the gap: g = max(1, int(g / 1.3)).
3. Walk through the list comparing a[i] with a[i + g]. Swap if the left one is bigger.
4. If the gap is 1 and a whole pass made no swaps, the list is sorted. Stop.
5. Otherwise go back to step 2.

Why 1.3? It was found by testing. Shrink the gap too slowly and you waste passes. Shrink it too fast and you lose the benefit of big jumps. About 1.3 works well in practice.

Time and space complexity

Each pass makes about n − g comparisons. Because the gap shrinks by 1.3 each time, it takes about log n passes to reach 1.

Best case, O(n log n): the list is already sorted, so no pass swaps anything. The sort runs through the shrinking gaps, about log n passes of about n comparisons each, then stops after the first pass at gap 1.

Average and worst case, O(n²): in theory there is no guarantee. Once the gap reaches 1, comb sort is bubble sort, and some inputs still need many passes at that stage. In practice comb sort is much faster than bubble sort and often close to O(n log n) on random data.

Space is O(1). It sorts in place with a gap, an index and a flag.

Common mistakes

• Stopping when the gap reaches 1. You must keep going at gap 1 until a whole pass makes no swaps.
• Letting the gap reach 0. Always clamp it with max(1, …).
• Looping i up to n instead of n − g, which reads past the end of the list.
• Expecting it to be stable. Swaps across a gap can jump a value over an equal one, so comb sort is not stable.

Comb sort vs. shell sort

Both use shrinking gaps, and they are easy to mix up. Comb sort does one bubble-style pass per gap: compare, maybe swap, move on. Shell sort does a full insertion sort per gap, so each value keeps moving until it is in place for that gap.

Shell sort usually wins on speed. Comb sort is simpler to write and to remember.

When to use it

Comb sort is a good example of a small idea with a big effect: one extra variable turns bubble sort into something much faster. It is useful when you need a short, in-place sort and have no library, for example on a tiny embedded device.

Otherwise, use your language’s built-in sort. It is faster and stable.

Questions

Why is it called comb sort?

The wide gaps are like the widely spaced teeth of a comb working through tangles first, before the fine teeth finish the job.

Is comb sort stable?

No. A swap across a gap can move a value past an equal one.

What is the shrink factor in comb sort?

The number the gap is divided by each pass. 1.3 is the common choice because it tests well in practice.