Comb Sort

Average time complexity - Ω(n^2/2^p)

Best-Case time complexity - Θ(n * log(n))

Worst-Case time complexity - O(n^2)

Worst-case space complexity - O(1)

Comb Sort is a variation of Bubble Sort that doesn't swap elements right next to each other, but rather calculates an optimal distance and then swaps two elements that are such a distance apart.

The gap also decays over time, down to gap 1. The decay is usually at an inverse exponential rate. It starts out as the size of the array (so the first pass swaps the first and last elements if they are out of order). Empirical testing has shown that dividing the gap by 1.3 every pass (or multiplying by (10 / 13) is the most efficient).

Lets say we have array:

4, 1, 5, 2, 3

On the first pass, comb sort will compare the first and fourth elements, because gap size is the size of the array divided by 1.3 (which is 3.8, rounds down to 3). This rounds down to 3 because the gap is stored as an integer, which discards all information after the decimal point. Since the gap is 3, the first element is compared with the element 3 spots after it. They are out of order, so they get swapped.

2, 1, 5, 4, 3

Now it compares the second and fifth elements, which are in order. Notice that increased the indices of both the left and the right elements that it is comparing.

The first pass is over, so it divides the gap (which is 3) again. The new gap is 2.3, which rounds down to 2.

It compares the first element with the third element. These are correct. Then it compares the second and fourth, which are also both correct. Finally, it compares the third and fifth elements, which are out of order, so it swaps them.

2, 1, 3, 4, 5

Now that this pass is complete, it divides the gap by 1.3 again. This yields a gap of 1.53, which rounds down to 1. The sort now effectively performs Bubble Sort, and the algorithm ensures that gap is always minimum 1.

The first and second elements are out of order, so it swaps them.

1, 2, 3, 4, 5

It then compares the second and third, third and fourth, fourth and fifth. These are all in order. Even though it is sorted, it goes through one more iteration. It will then exit because nothing was swapped in that iteration, so it means that the array is sorted.