Counting Sort Visualization

Counting Sort counts how many times each value occurs, then writes the values back in order.

How it works

Counting Sort works when the values are small integers. It makes one pass to count how often each value appears, turns the counts into starting positions, and then writes every value straight into its slot.

That is n + k work, where k is the range of values, and no comparisons at all. When k is small compared with n it is extremely fast; when the range is huge it wastes memory. It is stable in its standard form and is used as the inner step of Radix Sort.

What to watch for

Watch a quick scan over everything, then the rainbow is written out cleanly from one end to the other.

Complexity

Best

n + k

Average

n + k

Worst

n + k

Extra space

k

Stable

Yes

Race it

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

FAQ