Counting and Radix Sort
Comparison sorts cannot beat n log n, but they are not the only way to sort. If the keys are small integers, count how many times each one occurs, turn the counts into running totals, and every element can be dropped straight into its final position in one more pass: no comparisons at all. Walking the input backwards while placing keeps equal keys in their original order, and that stability is what radix sort relies on when it repeats the pass digit by digit, least significant first.
Counting sort on 7 keys from 0 to 9. No element is ever compared with another: the cnt row tallies each key, the tallies become running totals, and every element is then written straight to its final place in out.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 7, with their answers.
in[6] = 1 has key 1 and count[1] is 1. Which output index does it get?
Answer: 0. Decrement first, then place: count[1] - 1 = 0.
in[5] = 3 has key 3 and count[3] is 5. Which output index does it get?
Answer: 4. Decrement first, then place: count[3] - 1 = 4.
in[4] = 3 has key 3 and count[3] is 4. Which output index does it get?
Answer: 3. Decrement first, then place: count[3] - 1 = 3.
in[3] = 8 has key 8 and count[8] is 7. Which output index does it get?
Answer: 6. Decrement first, then place: count[8] - 1 = 6.
in[2] = 2 has key 2 and count[2] is 3. Which output index does it get?
Answer: 2. Decrement first, then place: count[2] - 1 = 2.
in[1] = 2 has key 2 and count[2] is 2. Which output index does it get?
Answer: 1. Decrement first, then place: count[2] - 1 = 1.
in[0] = 4 has key 4 and count[4] is 6. Which output index does it get?
Answer: 5. Decrement first, then place: count[4] - 1 = 5.
How it runs, step by step
Counting sort on 7 keys from 0 to 9. No element is ever compared with another: the cnt row tallies each key, the tallies become running totals, and every element is then written straight to its final place in out.
Counting sort of 7 values.
in[0] = 4, key 4: count[4] becomes 1.
Tally 4, count of 4 is 1.
in[1] = 2, key 2: count[2] becomes 1.
Tally 2, count of 2 is 1.
in[2] = 2, key 2: count[2] becomes 2.
Tally 2, count of 2 is 2.
in[3] = 8, key 8: count[8] becomes 1.
Tally 8, count of 8 is 1.
in[4] = 3, key 3: count[3] becomes 1.
Tally 3, count of 3 is 1.
in[5] = 3, key 3: count[3] becomes 2.
Tally 3, count of 3 is 2.
in[6] = 1, key 1: count[1] becomes 1. Every element has been tallied without a single comparison.
Tally 1, count of 1 is 1.
Turn the tallies into running totals: count[k] = count[k - 1] + tally[k], so count[k] is the number of elements with key at most k. That is exactly one past where the last such element belongs in the output.
Running totals 0, 1, 3, 5, 6, 6, 6, 6, 7, 7.
in[6] = 1, key 1. count[1] drops to 0, and that is its slot: out[0] = 1.
Place 1 at output index 0.
in[5] = 3, key 3. count[3] drops to 4, and that is its slot: out[4] = 3.
Place 3 at output index 4.
in[4] = 3, key 3. count[3] drops to 3, and that is its slot: out[3] = 3. A later element with the same key already sits to its right, so going backwards keeps them in input order: stable.
Place 3 at output index 3.
in[3] = 8, key 8. count[8] drops to 6, and that is its slot: out[6] = 8.
Place 8 at output index 6.
in[2] = 2, key 2. count[2] drops to 2, and that is its slot: out[2] = 2.
Place 2 at output index 2.
in[1] = 2, key 2. count[2] drops to 1, and that is its slot: out[1] = 2. A later element with the same key already sits to its right, so going backwards keeps them in input order: stable.
Place 2 at output index 1.
in[0] = 4, key 4. count[4] drops to 5, and that is its slot: out[5] = 4.
Place 4 at output index 5.
Sorted: 1, 2, 2, 3, 3, 4, 8. Two passes over n elements and one over k = 10 keys: O(n + k), below the comparison bound of n log n, at the price of needing small integer keys.
Sorted output 1, 2, 2, 3, 3, 4, 8.
Remember
- Counting sort: tally each key, prefix-sum the tallies, then place each element at count[key] - 1.
- Place backwards so equal keys keep their input order: the pass is stable.
- Radix sort is a stable counting sort per digit, least significant first; d digits give O(d x (n + k)).
Topics covered
Where this is used
TextSuffix arrays and the Burrows-Wheeler transform
Building a suffix array by prefix doubling sorts pairs of ranks, and those ranks are integers bounded by the text length, so each round is a counting sort instead of a comparison sort over strings. Compressors and aligners lean on that: bzip2's block sorter opens by tallying every two-byte prefix into a frequency table and turning those tallies into bucket offsets, which is a counting sort with k = 65536, and the FM-index behind read aligners like BWA and Bowtie is built from the same suffix ordering.
GraphicsSorting on GPUs
Radix sort is the default GPU sort because it never branches on a comparison: a pass is a histogram, a prefix sum and a scatter, which are exactly the primitives thousands of lanes run well in lockstep. NVIDIA's CUB DeviceRadixSort, which Thrust dispatches to for integer keys, works this way, and ray tracers use it to sort Morton codes when building a bounding volume hierarchy each frame.
DatabasesColumn sorts in analytical databases
ClickHouse carries a radix sort in RadixSort.h and uses it for ORDER BY on a single numeric column, and Spark's shuffle sorter packs each record's partition id and pointer into one long, then radix-sorts on the partition id bytes alone. When the key is a fixed-width number, a comparison sort spends nearly all its time in comparator calls and unpredictable branches, while a radix pass is a straight sequential scan over memory.
HardwareMail and punched card sorters
Radix sort goes back to Herman Hollerith's tabulating machines of 1887 and the card sorters that followed, which fed punched cards past one column at a time into a fixed set of bins, one pass per column. The name itself points at the radix, the base the key is written in. Postal sorters run the same loop over the digits of a barcode. The hardware constraint is exactly the one counting sort assumes: a small fixed number of output bins, one key position per pass, and stability across passes so that later digits do not scramble the earlier ones.
Why it works this way
Why walk the input backwards when placing?
After the prefix sums, count[k] is the number of keys less than or equal to k, so it points just past the end of k's block in the output. Decrementing before each write fills that block from the right, which means the last equal element in the input lands rightmost and the original order of ties survives. Run the placement loop forwards and equal keys come out reversed: harmless for bare integers, fatal for radix sort, which depends on this stability.
Why least significant digit first, when we read numbers the other way?
Each pass is stable, so sorting by the tens digit leaves the ones-digit order untouched inside every tens group. Work from the ones upward and after the last pass the array is fully ordered, with no recursion and no bookkeeping between passes. Most significant digit first also works, but then each bucket is an independent subproblem you have to recurse into, so you carry a stack of ranges instead of d flat passes.
O(n + k) is only linear if k is small
The count array has one slot per possible key, so sorting arbitrary 32-bit integers in one counting pass would need four billion slots. Radix sort exists to dodge that: split the key into d digits in some base b, and each pass costs O(n + b) with b chosen small, typically 256 so a digit is one byte and d is 4 for a 32-bit key. The base is the real tuning knob - a bigger base means fewer passes but a larger count array and worse cache behaviour.
Negative numbers and floats silently break the digit split
The code extracts digits with (v / place) % 10, which produces negative digits for negative values and indexes outside the count array. The usual fixes are to offset every key by the minimum before sorting, or to sort by raw bytes and flip the sign bit so the negative range orders below the positive one. IEEE floats need a similar trick: flip the sign bit for positives and invert all bits for negatives, after which byte-wise radix order matches numeric order.
Read more
- Counting sortWikipedia
- Radix sortWikipedia
- String sorts: LSD and MSD radixAlgorithms, 4th Edition · algs4.cs.princeton.edu
- Radix sort visualisedUSF
- American flag sort, the in-place MSD variantWikipedia