Comb sort

O(n² / 2^p)

Comb sort speeds up bubble sort by first comparing elements far apart (a large gap) and shrinking the gap by ~1.3× each round until it reaches 1. The big early gaps quickly remove small values stuck near the end, so the final near-bubble pass has little left to do.

Array
Edit the input and press Play

How it works

  1. Start with a gap as large as the whole array.
  2. Compare and swap elements that far apart, sweeping left to right.
  3. Shrink the gap (divide by ~1.3) and repeat.
  4. Once the gap is 1 and a pass makes no swaps, the array is sorted.

Pseudocode

1combSort(a):                        # O(n² / 2^p)2  gap ← n; swapped ← true3  while gap > 1 or swapped:4    gap ← max(1, floor(gap / 1.3))   # shrink the gap5    swapped ← false6    for i from 0 while i+gap < n:7      if a[i] > a[i+gap]: swap; swapped ← true