Comb Sort
See bubble sort compare far-apart values first, with a gap that shrinks each pass until it settles on neighbours.
How it works
Comb sort is bubble sort with a gap. Instead of comparing neighbours, each pass compares values that are gap positions apart and swaps them if they are out of order. The gap starts at the array length and shrinks by a factor of about 1.3 after every pass. Once it reaches 1, comb sort is plain bubble sort, and it stops after a pass with no swaps.
The big early gaps fix bubble sort's weak spot, the "turtles": small values near the end that bubble sort can only move one step left per pass. With a large gap, a turtle jumps most of the way to the front in a single swap, so by the time the gap is 1 the array is nearly sorted.
When to use it
Comb sort is a simple upgrade over bubble sort that runs much faster on random data, with the same tiny code size. For real work, the built-in sort is still the better choice.
Complexity
It is not stable: a swap across a gap can carry a value past an equal one. For example, with a gap of 2, sorting [2a, 2b, 1] swaps 2a with 1, giving [1, 2b, 2a].
| Case | Time | When |
|---|---|---|
| Best | O(n log n) | Already sorted: one pass per gap, with no swaps |
| Average | O(n² / 2ᵖ) | Random order: far faster than bubble sort in practice |
| Worst | O(n²) | Rare inputs where small values are left for the last passes |
Here p is the number of gap shrinks.
| Extra space | Why |
|---|---|
| O(1) | It swaps values in place, using a few loop variables |
Implementations
function combSort(array) {
let gap = array.length;
let sorted = false;
while (!sorted) {
gap = Math.floor(gap / 1.3);
if (gap <= 1) {
gap = 1;
sorted = true;
}
for (let i = 0; i + gap < array.length; i++) {
if (array[i] > array[i + gap]) {
[array[i], array[i + gap]] = [array[i + gap], array[i]];
sorted = false;
}
}
}
return array;
}
def comb_sort(array):
a = list(array)
gap = len(a)
is_sorted = False
while not is_sorted:
gap = int(gap / 1.3)
if gap <= 1:
gap = 1
is_sorted = True
for i in range(len(a) - gap):
if a[i] > a[i + gap]:
a[i], a[i + gap] = a[i + gap], a[i]
is_sorted = False
return a
#include <utility>
#include <vector>
std::vector<int> combSort(std::vector<int> a) {
const int n = static_cast<int>(a.size());
int gap = n;
bool sorted = false;
while (!sorted) {
gap = static_cast<int>(gap / 1.3);
if (gap <= 1) {
gap = 1;
sorted = true;
}
for (int i = 0; i + gap < n; i++) {
if (a[i] > a[i + gap]) {
std::swap(a[i], a[i + gap]);
sorted = false;
}
}
}
return a;
}