Comb Sort

An improvement over bubble sort that uses a gap larger than 1 to eliminate small values near the end of the list (turtles). The gap shrinks by a factor of 1.3 each pass until it reaches 1, at which point the algorithm becomes a standard bubble sort.

Algorithm Information

Time Complexity

Best: O(n log n)
Average: O(n²/2^p)
Worst: O(n²)

Space Complexity

O(1)

Properties

• Unstable sorting algorithm
• In-place sorting
• Gap-based bubble sort improvement
• Eliminates small values at end (turtles)
1/39
Speed: 1x

Algorithm Code

1function combSort(arr) {
2  const n = arr.length;
3  let gap = n;
4  const shrink = 1.3;
5  let sorted = false;
6 
7  while (!sorted) {
8    // Shrink gap by factor
9    gap = Math.floor(gap / shrink);
10    if (gap <= 1) {
11      gap = 1;
12      sorted = true;
13    }
14 
15    // Compare elements gap apart
16    let i = 0;
17    while (i + gap < n) {
18      if (arr[i] > arr[i + gap]) {
19        [arr[i], arr[i + gap]] = [arr[i + gap], arr[i]];
20        sorted = false;
21      }
22      i++;
23    }
24  }
25 
26  return arr;
27}

Variable State

n:7
gap:7
shrink:1.3
sorted:false

Call Stack

combSort

Array Visualization

Watch how Comb Sort processes the array step by step

64
0
34
1
25
2
12
3
22
4
11
5
90
6

Statistics

Comparisons0
Swaps0
Step1 / 39

Legend

Comparing
Active / Swapping
Sorted
Unsorted

Starting comb sort algorithm

How Comb Sort Works

Learn the fundamentals of comb sort through step-by-step explanations, code examples, and key concepts.