AlgoLab

Cycle sort

Cycle sort divides the array into permutation cycles: chains of positions where each value belongs in the next position in the chain. For each position, it counts how many later values are smaller to work out exactly where the value here belongs, then writes it there in one move, displacing whatever value was already occupying that spot, and follows that displaced value around the same cycle until the cycle closes.

When it is the right choice

Cycle sort earns a place whenever writes are drastically more expensive than reads — writing to flash memory with a limited erase-cycle lifetime, for instance — since it makes the theoretical minimum number of writes: one per value that is not already in its final position, and none at all for a value already there. It is a poor general-purpose choice otherwise: it still performs the same O(n²) comparisons as selection sort in every case, sorted or not, so when reads and writes cost about the same it is not competitive with insertion sort or any O(n log n) sort.

How it works

• For each starting position, in turn, remember the value there as the one currently being placed.
• Compare it with every later value to count how many are smaller — that count is the position it belongs at.
• If it already belongs at the starting position, no write is needed at all; move on to the next starting position.
• Otherwise, skip past any positions already holding an equal value, then write the value into the position it counted its way to, displacing whatever value was there.
• Repeat the counting and writing for the displaced value, following the same cycle, until a write lands back on the starting position and the cycle closes.

Worth noticing

• Its writes counter is the entire reason to use it: on the same shuffled input, cycle sort writes strictly fewer times than selection sort, even though selection sort also minimises swaps — cycle sort writes each value into its final position exactly once, where selection sort writes twice per exchange.
• It pays for those few writes with the same O(n²) comparisons as selection sort in every case — sorted, reversed or random — since it must scan the remaining values to count rank regardless of whether a write turns out to be needed.
• It is not stable: following a cycle can place an equal value past another equal value that has not yet been reached in the same cycle.

Cost

Best

O(n²)

Average

O(n²)

Worst

O(n²)

Extra space

O(1)

Stable

No

Worth comparing

• Selection sort — The sharpest contrast available: both minimise something, but selection sort minimises swaps while still writing twice per swap, and cycle sort minimises writes outright.
• Counting sort — A different way to spend reads to save writes: counting sort avoids comparisons altogether at the cost of counting space, where cycle sort keeps the comparisons and cuts writes instead.

All algorithms