Comb Sort is a sorting algorithm really similar to Bubble Sort. It highly improves its performances by removing the "turtles", that is the small elements placed near the end of the data structure that slows down a lot the performances of Bubble Sort.

Bubble Sort is based on comparing adjacent elements, so with a distance of 1. Comb Sort increases this distance using a shrink factor k (usually with a value of 1.3). Initially, the distance has a value of n. For each iteration, a Bubble Sort gets executed using the new distance value instead of 1. The distance gets progressively divided by the shrink factor k.

This procedure gets executed until the distance reaches the value of 1. At this point, the algorithm is a regular Bubble Sort, but the majority of the "turtles" already got removed.

Its average time complexity depends, in addition to the number of elements of the data structure, by a value p, representing the number of divisions carried out.