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.
Radix sort on 7 numbers up to two digits. Each pass is a stable counting sort by one digit, ones first, then tens. Stability is what makes it work: after the tens pass, numbers with the same tens digit are still in ones order from the pass before.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 14, with their answers.
in[6] = 25 has ones digit 5 and count[5] is 4. Which output index does it get?
Answer: 3. Decrement first, then place: count[5] - 1 = 3.
in[5] = 45 has ones digit 5 and count[5] is 3. Which output index does it get?
Answer: 2. Decrement first, then place: count[5] - 1 = 2.
in[4] = 18 has ones digit 8 and count[8] is 6. Which output index does it get?
Answer: 5. Decrement first, then place: count[8] - 1 = 5.
in[3] = 27 has ones digit 7 and count[7] is 5. Which output index does it get?
Answer: 4. Decrement first, then place: count[7] - 1 = 4.
in[2] = 15 has ones digit 5 and count[5] is 2. Which output index does it get?
Answer: 1. Decrement first, then place: count[5] - 1 = 1.
in[1] = 89 has ones digit 9 and count[9] is 7. Which output index does it get?
Answer: 6. Decrement first, then place: count[9] - 1 = 6.
in[0] = 53 has ones digit 3 and count[3] is 1. Which output index does it get?
Answer: 0. Decrement first, then place: count[3] - 1 = 0.
in[6] = 89 has tens digit 8 and count[8] is 7. Which output index does it get?
Answer: 6. Decrement first, then place: count[8] - 1 = 6.
in[5] = 18 has tens digit 1 and count[1] is 2. Which output index does it get?
Answer: 1. Decrement first, then place: count[1] - 1 = 1.
in[4] = 27 has tens digit 2 and count[2] is 4. Which output index does it get?
Answer: 3. Decrement first, then place: count[2] - 1 = 3.
in[3] = 25 has tens digit 2 and count[2] is 3. Which output index does it get?
Answer: 2. Decrement first, then place: count[2] - 1 = 2.
in[2] = 45 has tens digit 4 and count[4] is 5. Which output index does it get?
Answer: 4. Decrement first, then place: count[4] - 1 = 4.
in[1] = 15 has tens digit 1 and count[1] is 1. Which output index does it get?
Answer: 0. Decrement first, then place: count[1] - 1 = 0.
in[0] = 53 has tens digit 5 and count[5] is 6. Which output index does it get?
Answer: 5. Decrement first, then place: count[5] - 1 = 5.
How it runs, step by step
Radix sort on 7 numbers up to two digits. Each pass is a stable counting sort by one digit, ones first, then tens. Stability is what makes it work: after the tens pass, numbers with the same tens digit are still in ones order from the pass before.
Radix sort with 2 passes.
in[0] = 53, ones digit 3: count[3] becomes 1.
Tally 53, count of 3 is 1.
in[1] = 89, ones digit 9: count[9] becomes 1.
Tally 89, count of 9 is 1.
in[2] = 15, ones digit 5: count[5] becomes 1.
Tally 15, count of 5 is 1.
in[3] = 27, ones digit 7: count[7] becomes 1.
Tally 27, count of 7 is 1.
in[4] = 18, ones digit 8: count[8] becomes 1.
Tally 18, count of 8 is 1.
in[5] = 45, ones digit 5: count[5] becomes 2.
Tally 45, count of 5 is 2.
in[6] = 25, ones digit 5: count[5] becomes 3. Every element has been tallied without a single comparison.
Tally 25, count of 5 is 3.
Turn the tallies into running totals: count[k] = count[k - 1] + tally[k], so count[k] is the number of elements with ones digit at most k. That is exactly one past where the last such element belongs in the output.
Running totals 0, 0, 0, 1, 1, 4, 4, 5, 6, 7.
in[6] = 25, ones digit 5. count[5] drops to 3, and that is its slot: out[3] = 25.
Place 25 at output index 3.
in[5] = 45, ones digit 5. count[5] drops to 2, and that is its slot: out[2] = 45. A later element with the same ones digit already sits to its right, so going backwards keeps them in input order: stable.
Place 45 at output index 2.
in[4] = 18, ones digit 8. count[8] drops to 5, and that is its slot: out[5] = 18.
Place 18 at output index 5.
in[3] = 27, ones digit 7. count[7] drops to 4, and that is its slot: out[4] = 27.
Place 27 at output index 4.
in[2] = 15, ones digit 5. count[5] drops to 1, and that is its slot: out[1] = 15. A later element with the same ones digit already sits to its right, so going backwards keeps them in input order: stable.
Place 15 at output index 1.
in[1] = 89, ones digit 9. count[9] drops to 6, and that is its slot: out[6] = 89.
Place 89 at output index 6.
in[0] = 53, ones digit 3. count[3] drops to 0, and that is its slot: out[0] = 53.
Place 53 at output index 0.
Pass 2: the output of the ones pass becomes the input, 53, 15, 45, 25, 27, 18, 89, and the counts reset. Now sort by the tens digit.
Second pass by the tens digit.
in[0] = 53, tens digit 5: count[5] becomes 1.
Tally 53, count of 5 is 1.
in[1] = 15, tens digit 1: count[1] becomes 1.
Tally 15, count of 1 is 1.
in[2] = 45, tens digit 4: count[4] becomes 1.
Tally 45, count of 4 is 1.
in[3] = 25, tens digit 2: count[2] becomes 1.
Tally 25, count of 2 is 1.
in[4] = 27, tens digit 2: count[2] becomes 2.
Tally 27, count of 2 is 2.
in[5] = 18, tens digit 1: count[1] becomes 2.
Tally 18, count of 1 is 2.
in[6] = 89, tens digit 8: count[8] becomes 1. Every element has been tallied without a single comparison.
Tally 89, count of 8 is 1.
Turn the tallies into running totals: count[k] = count[k - 1] + tally[k], so count[k] is the number of elements with tens digit at most k. That is exactly one past where the last such element belongs in the output.
Running totals 0, 2, 4, 4, 5, 6, 6, 6, 7, 7.
in[6] = 89, tens digit 8. count[8] drops to 6, and that is its slot: out[6] = 89.
Place 89 at output index 6.
in[5] = 18, tens digit 1. count[1] drops to 1, and that is its slot: out[1] = 18.
Place 18 at output index 1.
in[4] = 27, tens digit 2. count[2] drops to 3, and that is its slot: out[3] = 27.
Place 27 at output index 3.
in[3] = 25, tens digit 2. count[2] drops to 2, and that is its slot: out[2] = 25. A later element with the same tens digit already sits to its right, so going backwards keeps them in input order: stable.
Place 25 at output index 2.
in[2] = 45, tens digit 4. count[4] drops to 4, and that is its slot: out[4] = 45.
Place 45 at output index 4.
in[1] = 15, tens digit 1. count[1] drops to 0, and that is its slot: out[0] = 15. A later element with the same tens digit already sits to its right, so going backwards keeps them in input order: stable.
Place 15 at output index 0.
in[0] = 53, tens digit 5. count[5] drops to 5, and that is its slot: out[5] = 53.
Place 53 at output index 5.
Sorted: 15, 18, 25, 27, 45, 53, 89. 2 passes of O(n + 10) each, so O(d x (n + k)) for d-digit numbers, still linear for a fixed number of digits.
Sorted output 15, 18, 25, 27, 45, 53, 89.
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