Comparison sorts can never beat n log n. Counting sort cheats in a legal way: when the keys are small integers, it does not compare at all and sorts in linear time.
The idea, the mechanics and the cost.
Suppose every value is an integer between 0 and k − 1, for example exam grades or ages. Make an array count of size k, all zeros. Scan the input once and for each value v do count[v]++.
For [3, 6, 1, 3, 4, 1, 6, 3] this gives count = [0, 2, 0, 3, 1, 0, 2]: two 1s, three 3s, one 4, two 6s.
If you only need the sorted numbers, you are already done: write each v out count[v] times. Two simple passes, O(n + k), and not a single comparison between elements.
Usually you sort records by a key (people by age), so you need positions, not just counts.
Turn count into a prefix sum: count[v] becomes "how many keys are ≤ v". Then the elements with key v occupy output slots count[v−1] … count[v] − 1. In the example the 3s take slots 2, 3 and 4.
Now scan the input from right to left: for each element with key v, decrement count[v] and put the element at out[count[v]]. Going right to left places the last 3 in the last 3-slot, so equal keys keep their input order: counting sort is stable.
That stability is what makes radix sort work: sort numbers by their last digit, then the next digit, and so on, each time with a stable counting sort.
Any sort that learns about the order only by comparing two elements needs about n log n comparisons in the worst case. There are n! possible orders, and each yes/no comparison can at best halve the candidates, so log₂(n!) ≈ n log n questions are needed.
Counting sort escapes this bound because it uses the keys as array indices, which a comparison sort cannot do.
The price is the k term in O(n + k) time and memory. Grades 0..100 or ages 0..120 are perfect. Values up to 10⁹, phone numbers or strings are not: the count array would be enormous. Then use a normal O(n log n) sort, or radix sort if keys are fixed-size integers. A useful trick: if values are large but few, compress them first (sort the distinct values and replace each by its rank).
The lecture as a narrated explainer video.
The video follows the lecture slide by slide: the same example, the same notation. Use it before or after playing with the visualizer.
Step through the algorithm, then try it on your own input.
👀 What to watch: Three phases: count, prefix sum, place. In the last phase notice the scan goes right to left and each count goes down by one.
| v | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| count | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 count occurrences of each value 0..k-1 2 prefix-sum count[] → count[v] = #(≤ v) 3 scan input right→left: out[--count[v]] = v 4 // zero comparisons between elements
Three questions. Pick an answer to see why.
Real problems to lock it in, easiest first.