Counting sort
Scenario
A school has 1,000,000 students and wants them in order of age. Every age is a whole number between 5 and 18.
Do you really need to compare students with each other to sort them?
Overview
A non-comparison sorting algorithm for integer keys in a known small range, running in `O(n + k)` time.
It beats the `O(n log n)` comparison limit when the range of keys is small, and its stable form is the building block of radix sort.
Where used: Sorting by small integer keys: ages, grades, scores, characters (`k = 26` or `256`), The digit-by-digit passes inside radix sort, Building histograms and cumulative counts
Why it exists
Problem: Comparison sorts such as merge sort and quick sort cannot go below `O(n log n)`, because each comparison only gives one yes-or-no answer. For a million items that is about twenty million comparisons, even when the keys are tiny numbers.
Naive approach: Run a general comparison sort and ignore the fact that the keys come from a small range.
Better idea: When the keys are whole numbers in a small range `0..k`, use the key itself as an index. Count how many items have each key, turn the counts into final positions, and place every item straight into its slot with no comparisons at all. That is `O(n + k)`.
Why learn this
- It shows that the `O(n log n)` limit only applies to comparison sorts.
- The count, prefix sum and place pattern shows up in radix sort, suffix arrays and many frequency problems.
- Interviewers use it to check that you spot a small range and use it.
Mental model
Do not compare, count. Tally how many of each value there are, then work out where each value's block starts in the output.
Make an array `count` with one slot per possible key. Pass 1 counts how many items have each key. Pass 2 turns the counts into running totals, so `count[v]` becomes the number of items with key at most `v`, which is the index just past where the block of `v` ends in the output. Pass 3 walks the input from right to left and drops each item at the end of its block, moving that end one step left each time. Walking right to left is what keeps equal keys in their original order.
Repeated decision: Where does the block for this key start, and how many slots of it are already filled?
Deep dive
Start with the simple version, which is enough when you are sorting plain integers. Make `count` with `k + 1` zeros. For each value `x` in the input do `count[x] += 1`. Then write the output: for each `v` from `0` to `k`, append `v` to the output `count[v]` times.
For `[3, 1, 3, 0, 2, 1, 3]` with keys `0..3`, `count` is `[1, 2, 1, 3]`, and the output is `[0, 1, 1, 2, 3, 3, 3]`.
This version rebuilds values from counts. It cannot sort records (a student object with an age), because the object itself is not kept. For that you need the stable version.
The stable version keeps the items themselves and has three passes.
Pass 1: count the keys, as before. For the input above, `count = [1, 2, 1, 3]`.
Pass 2: turn `count` into running totals, so each slot holds how many items have a key at most that value: `count = [1, 3, 4, 7]`. Read it this way: the items with key `0` fill output positions up to index 0, key `1` up to index 2, key `2` up to index 3, key `3` up to index 6. Each `count[v]` is one past the last slot for `v`.
Pass 3: go through the input from the last item to the first. For an item with key `v`, decrement `count[v]` and put the item at that index in the output.
for i from n - 1 down to 0:
v = key(a[i])
count[v] -= 1
out[count[v]] = a[i]
The result is `[0, 1, 1, 2, 3, 3, 3]`. Each item went directly to its final index, and no two items were ever compared.
Why go right to left? Take records `(3, 'a'), (1, 'b'), (3, 'c')`. After counting and running totals, the block for key 3 is the last two slots. Scanning from the right, `'c'` is placed first at the end of the block, then `'a'` goes just before it. The two items with key 3 end up as `'a'` then `'c'`, the same order as in the input. That is stability.
Scanning left to right would put `'a'` at the end of the block and `'c'` before it, so equal keys would reverse. For plain integers nobody can tell. For records, and for radix sort, which relies on each pass keeping the order from the earlier pass, it matters.
Negative numbers: array indexes cannot be negative, so subtract the minimum value from every key first. The key range is then `max - min + 1`, and you add the minimum back when writing the output.
Cost. The three passes are `O(n)`, `O(k)` and `O(n)`, so time is `O(n + k)`. The extra memory is the `count` array of size `k + 1` plus the output array of size `n`, so space is `O(n + k)`.
This is only good when `k` is not much larger than `n`. Sorting 20 numbers that lie between 0 and 1,000,000,000 would allocate a billion counters to sort 20 items, which is far worse than an `O(n log n)` sort. When keys are large integers, split them into digits and run counting sort on each digit in turn; that is radix sort, covered in `non-comparison-sorts`.
It also needs keys that map to integers. Arbitrary strings, floating point numbers and objects with no integer key do not fit, unless you first map them to small integers.
Key points
- Complexity: Time `O(n + k)`, extra space `O(n + k)`, where `k` is the size of the key range.
- Three passes: Count each key, convert counts to running totals (end positions), then place items from right to left.
- Stable when you scan right to left: Equal keys keep their input order. This is what lets radix sort use it for each digit.
- Needs a small integer range: If `k` is much bigger than `n`, the count array dominates and a comparison sort is better.
Pattern: Count, prefix sum, place
Recognition cues:
- Keys are integers in a small known range (or characters)
- Linear-time sort is requested
- Sorting must keep the order of equal keys (stable)
Failure signals
- A problem says values are between 0 and 100, or are lowercase letters, and asks for linear time sorting.
- You are about to run `O(n log n)` sorting on keys from a tiny range.
- A radix sort gives a wrong order, which usually means the digit pass was not stable.
Engineering examples
Radix sort passes
Sort millions of 32-bit integers faster than a comparison sort.
Radix sort sorts by one digit at a time (for instance 8 bits, so `k = 256`) and needs each pass to be stable. Stable counting sort is that pass.
Image histograms
Count how many pixels have each brightness from 0 to 255, and rank brightness levels.
Brightness is a small integer range, so counting pixels per level is one pass, and the running totals are exactly what histogram equalization uses.
When not to use
- The key range is much larger than the number of items: The `O(k)` counting pass and memory cost swamp the savings. Use a comparison sort or radix sort.
- Keys are floats, long strings or objects with no small integer key: There is no direct index to count into.
- Memory is tight and the data is huge: It needs a separate output array and a count array, so it is not in place.
Common mistakes
- Scanning left to right in the placement pass: With running totals as end positions, a left-to-right scan reverses equal keys, so the sort is not stable. Scan from the last item to the first.
- Forgetting that keys start at the minimum, not zero: A key of `-3` or `1000` used directly as an index crashes or wastes memory. Subtract the minimum so the keys start at `0`.
- Off-by-one in the count array size: For keys `0..k` you need `k + 1` slots. With `k` slots, the maximum key indexes out of range.
- Using it when the range is huge: A key range of a billion allocates a billion counters. Compare `k` with `n` before choosing it.
Recall questions
- What is counting sort's time and space complexity?
- Why can counting sort beat the `O(n log n)` limit of sorting?
- In the stable version, what do the running totals in `count` mean, and why do we scan the input from right to left?
- When is counting sort a bad choice?
- How do you handle negative numbers in counting sort?
Understanding checks
What is the `count` array after counting, and after the running totals, for the input `[2, 0, 2, 1, 2]` with keys `0..2`?
After counting: `[1, 1, 3]`. After running totals: `[1, 2, 5]`.
There is one 0, one 1 and three 2s. The running total adds each count to the sum before it: 1, 1 + 1 = 2, 2 + 3 = 5. The 5 says the block of 2s ends just before index 5.
A radix sort built on this counting sort sometimes returns a wrong order. What is the likely bug?
The placement pass scans from left to right, so the counting sort is not stable and equal digits undo the work of the earlier digit passes. Scan from right to left.
Radix sort relies on each pass keeping the order created by the earlier passes. A non-stable pass scrambles it.
You call counting sort on the array `[5, 1000000000]`. It runs but uses gigabytes of memory. Why?
The count array has one slot per possible key, so the range up to 1,000,000,000 allocates about a billion slots to sort two numbers.
Memory and time are `O(n + k)`. When `k` is huge compared with `n`, the `k` term dominates and counting sort is the wrong tool.
Questions & answers
Sort an array of one million ages, each between 0 and 120, in linear time.
Counting sort with `k = 120`: count the ages, then write each age out `count[age]` times. Time `O(n + 121)`, which is `O(n)`.
Approach: Spot the small key range, then do the count pass and the output pass.
Sort the characters of a lowercase string in linear time.
Count each letter in an array of 26, using `ord(c) - ord('a')` as the index, then rebuild the string letter by letter in order. Time `O(n + 26)`.
Approach: The alphabet is the small key range. This is also the first step of many anagram checks.
Sort a list of records by a small integer key while keeping the original order for equal keys, in `O(n + k)`.
Use the stable counting sort: count, convert to running totals, then place records scanning from the last to the first.
Approach: The right-to-left scan is what makes equal keys keep their input order.
Interesting facts
- Counting sort was described by Harold Seward in 1954 in his MIT work on sorting, and it is still the inner step of the fastest integer sorts.
- The `O(n log n)` lower bound is for sorting by comparisons: with `n!` possible orders and one yes-or-no answer per comparison, you need at least `log2(n!)` comparisons, which is about `n log n`.
Continue learning
Previous: Frequency Counting
Previous: Prefix Sums
Next: Non-comparison sorts
Related: Non-comparison sorts
Related: Frequency Counting
Related: Prefix Sums
Related: Quick sort
Related: Merge Sort