Comb Sort: Mechanism, Complexity Analysis & Interactive Visualizer

Comb Sort

An ingenious improvement on Bubble Sort: compares elements at a shrinking gap size to eliminate small values trapped near the end of the array ("turtles") before finishing with a final bubble pass.

How it works

Comb Sort, designed by Włodzimierz Dobosiewicz in 1980 and popularized by Stephen Lacey and Richard Box in 1991, addresses the core inefficiency of Bubble Sort: "turtles". In Bubble Sort, large values at the beginning move quickly ("rabbits"), but small values at the end move left very slowly ("turtles"). Comb Sort fixes this by comparing elements separated by a gap:

1. Initial Gap: Start with a gap equal to the array length \(n\).
2. Shrink Stage: On each pass, divide the gap by a shrink factor (proven mathematically to be optimal at \(\approx 1.3\)). If the gap drops below 1, set it to 1.
3. Compare and Swap: Traverse the array comparing elements at index \(i\) and \(i + \text{gap}\). Swap them if they are out of order.
4. Termination: Repeat the shrinking passes until the gap is 1 and a complete pass is made with zero swaps (reverting to a standard bubble sort checks).

Complexity

Interactive visualization

Pseudocode

procedure combSort(A):
  n ← length(A)
  gap ← n
  shrink ← 1.3
  sorted ← false
  
  while not sorted:
    gap ← floor(gap / shrink)
    if gap ≤ 1:
      gap ← 1
      sorted ← true  # assume sorted for the final bubble sort sweep
      
    i ← 0
    while i + gap < n:
      if A[i] > A[i + gap]:
        swap A[i], A[i + gap]
        sorted ← false
      i ← i + 1

JavaScript implementation

function combSort(arr) {
  const n = arr.length;
  let gap = n;
  const shrink = 1.3;
  let sorted = false;
  
  while (!sorted) {
    gap = Math.floor(gap / shrink);
    if (gap <= 1) {
      gap = 1;
      sorted = true;
    }
    
    let i = 0;
    while (i + gap < n) {
      if (arr[i] > arr[i + gap]) {
        [arr[i], arr[i + gap]] = [arr[i + gap], arr[i]];
        sorted = false;
      }
      i++;
    }
  }
  return arr;
}

Pros and cons

When (not) to use it

• Replacing simple sorts: Excellent if you need a quick sorting routine that is faster than Bubble Sort or Insertion Sort but requires zero complex stack/heap setups.
• Strictly stable lists: Do not use if duplicate order preservation is required.