Cycle Sort Visualization

Cycle Sort writes every value directly to its final position, using the fewest possible writes.

How it works

Cycle Sort counts how many values are smaller than the current value, which tells it exactly where that value belongs. It writes the value there, picks up the value it displaced, and repeats until the cycle comes back to where it started. Then it moves on to the next unsorted position.

Counting the smaller values takes O(n²) comparisons, so it is slow, but each value is written at most once. That makes it useful where writes are costly, such as flash memory that wears out with each write. It is not stable.

What to watch for

Watch values snap straight into their final places with no shuffling around, after long scans to find where each belongs.

Complexity

Best

n²

Average

n²

Worst

n²

Extra space

1

Stable

No

Race it

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

FAQ