Summary

Comb Sort is a significant improvement over Bubble Sort. It works by using a gap between compared elements that shrinks each pass by a shrink factor (typically 1.3). This allows it to move small values from the end of the list ("turtles") towards the beginning very quickly. Its average time complexity is often cited as $O(n^2 / 2^p)$, where p is the number of passes, showing a dramatic improvement over Bubble Sort's standard $O(n^2)$ average case. When the gap eventually reaches 1, it finishes with a final pass that is equivalent to a regular Bubble Sort on a nearly-sorted list.

How it Works

• 1. Initialize Gap: Start with a gap equal to the length of the array (n).

• 2. Choose Shrink Factor: A shrink factor of 1.3 is used to reduce the gap in each pass.

• 3. Loop Until Sorted: Continue the process as long as the gap is greater than 1, or if the last pass with a gap of 1 resulted in any swaps.

• 4. Shrink Gap: In each iteration, calculate the new gap by dividing the current gap by the shrink factor and taking the floor. If the calculated gap is less than 1, set it to 1.

• 5. Compare and Swap: Iterate through the array from the beginning, comparing elements at index i and i + gap. If the element at i is greater, swap them.

• 6. Final Pass: When the gap becomes 1, the algorithm behaves like Bubble Sort. It makes passes until one full pass completes with no swaps, at which point the array is sorted.