Cet article est actuellement en cours de traduction.
Suivez nous sur facebook : https://www.facebook.com/Hybesis.Urna
Ou rejoignez la communauté : https://community.hurna.io
Pour être notifié de sa mise à disposition.

Comb sort (or Dobosiewicz Sort) is similar to bubble sort in that is iterates through the sequence multiple times, swapping elements that are not ordered as it goes. The difference is that comb sort does not start off looking at adjacent elements but instead looks at elements with a certain distance, called the gap. This gap progressively shifts down as the algorithm continues

Similar to cocktail sort, comb sort improves upon bubble sort due to its ability to deal with the “turtles problem” (small elements near the end of the list slowing down the algorithm).
However it still retains the same worst case computational complexity.

One interesting thing to note however, is that Comb sort is almost as fast as a Quick Sort!

The gap is first equal to n, and after each iteration is reduced by a shrink factor (k) until it reaches the value of 1. Hence, at the very end, the Comb Sort behaves exactly like the Bubble Sort.

The shrink factor has a great effect on the efficiency of comb sort. k = 1.3 has been suggested as an ideal shrink factor by the authors of the original article after empirical testing on over 200,000 random lists. A value too small slows the algorithm down by making unnecessarily many comparisons, whereas a value too large fails to effectively deal with turtles, making it require many passes with 1 gap size.


  • 1. Set gap = n
  • 2. While there is swap needed:
    • 2.a. Shrink the gap by k such that gap always >= 1.
    • 2.b. Compare each pair of elements separated by the gap and if they are in reversed order, swap them.
    • 2.c. If gap = 1 and no swap made, then stop: we are done.


void CombSort (Iterator begin, Iterator end)
  auto distance = distance(begin, end);
  if (distance < 2)

  auto gap = distance;
  bool hasSwapped = true;
  while (hasSwapped)
    hasSwapped = false;

    // Compute new gap
    gap /= 1.3;
    if (gap > 1)
      hasSwapped = true;
      gap = 1;

    for (auto it = begin; it + gap < end; ++it)
      if (Compare(it, (it + gap)))
        swap(it, (it + gap));
        hasSwapped = true;

Usefull maths, Assymptotics of the generalized harmonic number Hn,r:

$$H_{n,r} = \sum_{k=1}^{n} \frac{1}{k^r}$$ For $$n \approx 1$$ $$H_{n,1} \in O(log(n))$$



The best configuration occurs when all elements are already sorted or nealy sorted.
In that case the loop with gap=1 will be run only once (as the others); let's read its sequences from the end of computation for a more convenient formulation:


$$a_n = n$$ $$a_(n-1) = n\frac{1}{1.3}$$ $$a_(n-2) = n\frac{1}{1.3^2}$$ $$a_(n-3) = n\frac{1}{1.3^3}$$ $$...$$ $$a_(n-i) = n\frac{1}{1.3^i}$$


Given the generalized harmonic number Hn,r $$\Theta \approx O(nlog(n))$$

Average / Worst

The average and worst case runtime of Comb sort (or Dobosiewicz sort) is O(n2). Proving this is a bit tricky, but has been proved using method based on Kolmogorov complexity (e.g. Survey by Vitanyi, page 16).


Comb Sort does not use any buffer nor does make any recursion. Thus, it requires O(1) space in all case.