Overview
Comb Sort is an improvement over Bubble Sort that addresses the problem of
turtles, or small values near the end of the list, which slow down the sorting
process. Comb Sort works by initially comparing elements that are far apart,
and gradually reducing the gap between elements to be compared as the
algorithm proceeds. The idea is to eliminate turtles early on and make the
list closer to being sorted before resorting to the traditional Bubble Sort
approach with a gap of 1.
Time Complexity:
Best case: O(n log n) - When the gap reduction efficiently eliminates inversions
Average case: O(n log n) - Similar to the best case, as the gap shrinks efficiently
Worst case: O(n²) - Similar to Bubble Sort when the array is initially in reverse order
Space Complexity: O(1) - It is an in-place sorting algorithm.
gap = length(list)shrinkFactor = 1.3swapped = truewhile (gap > 1 or swapped) gap = max(1, floor(gap / shrinkFactor)) swapped = false for i = 0 to length(list) - gap if list[i] > list[i + gap] swap(list[i], list[i + gap]) swapped = trueSHORT EXPLANATION------------------1. Set the initial gap size to the length of the list2. Reduce the gap size by dividing it by a shrink factor (typically 1.3)3. Compare each element with the element at the current gap distance - If the element is greater, swap them4. Continue the process, reducing the gap and performing swaps, until the gap is 1 and no swaps are needed, indicating the list is sorted5. The last pass is effectively a Bubble Sort with gap = 1