Comb sort is a comparison sorting algorithm. It is an exchange sort, similar to bubble sort.

In comb sort, gaps (distance of two items from each other) are introduced. The gap in bubble sort is 1. The gap starts out as a large value, and, after each traversal, the gap is lessened, until it becomes 1, where the algorithm basically degrades to a bubble sort. This idea can practically kill turtles because some of them would "jump" to the beginning of the list early on.

The shrink factor determines how much the gap is lessened. This value is crucial because a small value means that it would be slower for the gap to degrade to 1, slowing down the process, while a large value will not effectively kill turtles. An ideal shrink factor is 1.3.


comb_sort(list of t)
    gap = list.count
    temp as t
    swapped = false
    while gap > 1 or not swapped
        swapped = false
        if gap > 1 then
            gap = floor(gap/1.3)
        i = 0
        while i + gap < list.count
            if list(i) > list(i + gap)
                temp = list(i) // swap
                list(i) = list(i + gap)
                list(i + gap) = temp
            i += 1

 See Also Edit

Sorting algorithms
Bubble sort - Insertion sort - Merge sort - Quicksort - Selection sort - Heap sort -

Comb Sort