Heaps & gaps · Intermediate
Comb Sort
Compare far-apart items with a shrinking gap, then finish like Bubble Sort.
- Best
- O(n log n)
- Average
- About O(n²)
- Worst
- O(n²)
- Space
- O(1)
- Stability
- Not stable
- Memory model
- In-place
How it builds order
- Start with a gap near the array length.
- Compare values that gap apart.
- Shrink the gap by the factor 1.3.
- At gap 1, continue until no swap occurs.
Why it works
Wide gaps remove small values trapped near the end, a major weakness of one-direction Bubble Sort.
Watch for: The gap shrinks by about 1.3; gap 1 repeats until a pass makes no swaps.
The interactive version of this page adds the full trace, synchronized pseudocode, practice decisions, input experiments, and mastery review.