Comb sort
Comb sort is bubble sort with the comparison gap widened: instead of only ever comparing neighbours, it starts by comparing values a whole array-length apart and shrinks that gap by a factor of roughly 1.3 every pass, finishing with a gap of one, which is an ordinary bubble sort pass.
When it is the right choice
It is worth knowing as the natural next step from bubble sort once the turtle problem is understood, and it is a fair general-purpose exchange sort for a bit more implementation effort than bubble sort. It is not a serious competitor to shell sort, insertion sort, or any O(n log n) sort, and its final full pass at a gap of one still costs an ordinary O(n²) worst case just like bubble sort.
How it works
- Set the gap to the length of the array.
- Shrink the gap by dividing it by 1.3, rounding down, with a floor of one.
- Compare every pair of values that gap apart, from the start of the array to the end.
- Swap any pair found out of order.
- Repeat, shrinking the gap further each pass, until the gap is one and a pass makes no swaps.
Worth noticing
- A wide gap moves far-out-of-place values most of the way home in a single pass — the same turtle problem cocktail shaker sort solves by reversing direction instead, solved here by widening the reach of each comparison.
- A gap of one is exactly a bubble sort pass, so a poorly-behaved final stretch at gap one can still cost the full O(n²) bubble sort worst case.
- It is not stable: a wide gap can swap a value past an equal value several positions away, which adjacent-only comparisons in bubble sort or insertion sort never do.
Cost
- Best
- O(n log n)
- Average
- O(n²)
- Worst
- O(n²)
- Extra space
- O(1)
- Stable
- No