Counting Sort

By Victor Arce

Every sort so far has worked by comparing values. Counting sort doesn't — it sorts by where a value belongs, not by how it compares to others. If you know the values are small whole numbers, you can drop each into a labelled bin and then read the bins back in order. No comparisons, and it can beat the O(n log n) comparison-sort limit.

Step through it below with single digits (0–9). First each value drops into the bin matching it (distribute); then the bins are read left to right, 0 → 9 (collect), and the output comes out sorted. Toggle show log to follow along.

How it works

Counting sort needs values from a known, small range — here the digits 0..9, so there are 10 bins.

1. Distribute. Walk the input once; each value v goes into bin v. (The classic version keeps just a count per bin; showing the items themselves makes the idea concrete.)
2. Collect. Sweep the bins in order 0, 1, … 9, emitting everything in each bin to the output. Because the bins are visited in order, the output is sorted.

Keeping items in the order they arrived within each bin makes counting sort stableStable: equal values keep their original relative order after sorting. — important when it's used as the inner loop of radix sort.

Cost

With n items and a value range of size k, counting sort runs in O(n + k) time and uses O(n + k) extra space — linear when k is comparable to n. That beats the Ω(n log n) lower bound for comparison sorts, because it never compares two values; it exploits knowing the range. The catch is exactly that range: if k is huge (e.g. 32-bit integers) the bins are impractical — which is where radix sort comes in, applying counting sort one digit at a time.

Back to Sorting Algorithms