Home/Sorting/Comb sort
Search algorithmsCTRL K

Comb sort

· bubble sort with a shrinking gap
/sorting/comb-sort
COMPARISONS
0
so far
SWAPS
0
one per inversion fixed
GAP
24
distance between compared elements
PASS
0
one per gap value
SHRINK
1.3
gap ÷ factor each pass
comparingswappedin place
n = 24 · seed 7 · 201 steps
step 0 / 200
Size24
comb_sort.ts
1
function combSort(array: number[]) {
2
  let gap = array.length;
3
  let swapped = true;
4
  while (gap > 1 || swapped) {
5
    gap = Math.max(1, Math.floor(gap / 1.3));
6
    swapped = false;
7
    for (let i = 0; i + gap < array.length; i++) {
8
      if (array[i] > array[i + gap]) {
9
        swap(array, i, i + gap);
10
        swapped = true;
11
      }
12
    }
13
  }
14
}
CURRENT STEP
line 2

Start with gap = 24, the whole array. Comparing far apart first kills the small values stuck at the end.

// how it works

Understanding Comb sort

comb sort · compare far apart first, the turtles never form
01

The idea

Comb sort is bubble sort where the compared elements start far apart and the gap shrinks by a factor of 1.3 every pass until it reaches 1. Large gaps move small values from the far end to the front in a single swap, which is exactly what bubble sort cannot do.

By the time the gap is 1 the array is nearly sorted and the final bubble passes barely swap anything. The factor 1.3 comes from experiment: smaller factors do too many passes, larger ones leave too much for the end.

02

The four stages

1
shrinkgap ← ⌊gap / 1.3⌋, at least 1
2
comparearray[i] with array[i + gap]
3
swapout of order: exchange across the gap
4
finishgap 1 and a pass without swaps
03

Complexity

best
O(n log n)gap passes only
average
O(n² / 2ᵖ)p the number of gap passes; close to n log n in practice
worst
O(n²)pathological inputs exist
space
O(1)in place
04

Versus its siblings

COMPARISONS AT N = 1 000 · RANDOM INPUT
bubble
499,500
insertion
250,000
comb
22,000
quick
13,900
merge
8,700
same random input for every algorithm
05

Pseudocode

COMBSORT(array)
  gap ← n; swapped ← true
  while gap > 1 or swapped
    gap ← max(1, ⌊gap / 1.3⌋); swapped ← false
    for i ← 0 while i + gap < n: if array[i] > array[i + gap]: swap them; swapped ← true
06

When to use

A tiny in-place sort that is fast enough: microcontrollers, early game consoles, sorting a few thousand records.
As a demonstration that the gap idea alone turns O(n²) into something close to O(n log n).
07

Pitfalls

Not stable: equal values can cross each other over a gap.
The loop must continue after gap reaches 1 until a pass makes no swap.
The gap 9 and 10 are slow spots; the rule 11 variant skips them by turning 9 or 10 into 11.
08

History

Włodzimierz Dobosiewicz published the idea in 1980; Stephen Lacey and Richard Box rediscovered it in 1991 and named it comb sort in a Byte magazine article, where they found the 1.3 shrink factor by simulation. It is Shell sort's idea applied to bubble sort instead of insertion sort.

Back to Sorting