Comb Sort Visualization

Comb Sort is Bubble Sort with a shrinking gap: it compares values far apart first, then closer ones.

How it works

Bubble Sort is slow because small values near the end (called turtles) move only one step per pass. Comb Sort compares values a large gap apart instead, so turtles jump most of the way at once. After each pass the gap shrinks by a factor of about 1.3, and once it reaches one, Comb Sort finishes with ordinary bubble passes.

The shrinking gap makes it much faster than Bubble Sort on random data, close to n log n in practice, while keeping the same tiny in-place loop. It is not stable.

What to watch for

Watch the picture go from noise to a rough rainbow in a few big sweeps, then the last passes clean up the details.

Complexity

Best

n log n

Average

n²/2^p

Worst

n²

Extra space

1

Stable

No

Race it

Same shuffle, same speed, one winner: Comb vs Bubble. Or open the studio to try other layouts, sizes and speeds, and make a video of it.

FAQ