**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.

## AlgorithmEdit

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

## ExampleEdit

Sorting the list: 5, 7, 9, 10, 3, 1, 4, 8, 2, 6. Shrink factor: 1.24:

- 57910314826

- Iteration 1. Gap = 8

- 27910314856
- 26910314857

- Iteration 2. Gap = 6

- 26910314857
- 26910314857
- 26510314897
- 26573148910

- Iteration 3. Gap = 4

- 26573148910
- 21573648910
- 21473658910
- 21473658910
- 21473658910
- 21473658910

- Iteration 4. Gap = 3

- 21473658910
- 21473658910
- 21473658910
- 21453678910
- 21453678910
- 21453678910
- 21453678910

- Iteration 5. Gap = 2

- 21453678910
- 21453678910
- 21354678910
- 21354678910
- 21354678910
- 21354678910
- 21354678910
- 21354678910

- Iteration 6. Gap = 1

- 12354678910
- 12354678910
- 12345678910
- 12345678910
- 12345678910
- 12345678910
- 12345678910
- 12345678910

- Iteration 7

Since the items are already sorted, no swaps will be made in this iteration and the algorithm ends.