Counting sort and radix sort

The USGS catalogue has 19,073 earthquakes of magnitude 5 and above for 2015–2025. Merge sort orders them by magnitude in 255,585 comparisons. But magnitude is recorded to hundredths and lies between 5.00 and 8.80: it has only 381 possible values. Set up a counter for each and count how many earthquakes of each magnitude there are. Then the answer can be written out at once: first all the 5.00s, then all the 5.01s, and so on up to 8.80. Not a single comparison.

The whole count takes 38,527 steps: a pass over the catalogue, 381 additions and one more pass. Look at the magnitude counters. On a logarithmic scale they line up almost straight: from 5.0 to 5.9 there are 17,595 earthquakes, from 6.0 to 6.9 1325, from 7.0 to 7.9 145, 8.0 and above 8. Each unit of magnitude has about ten times fewer: this is the Gutenberg–Richter law, and the sort builds its histogram on the way. Switch the key to depth: the tall peak at 10 km is not geology but a convention of the catalogue. If the depth cannot be determined from the stations' records, USGS puts a nominal 10 km.

The idea

If the keys are integers from a small range, there is no need to compare them. Count how many elements have each key; the prefix sums of these counters tell where in the answer each key's block begins; in a second pass put each element in the first free place of its block. If the keys are long, split them into digits and sort by each digit with counting, one per pass.

Counting sort has three steps, each one simple.

1. Count. An array count of k zeros; for each element, count[key] += 1.
2. Addresses. Prefix sums: start[v] = how many elements have a key smaller than v. This is the cell at which the block of key v begins in the answer.
3. Lay out. Go through the input from left to right; put an element with key v into out[start[v]] and increase start[v].

The main property hides in the third step. Elements with equal keys go into their block in the same order as in the input: the sort is stable. In the first scene you can see it by colour: the catalogue is in time order, and within each block the colours go from dark to light. Switch the layout to “from the block end”: the answer is still sorted by magnitude, but within the blocks time runs backwards. For a single sort the difference may not matter. For radix sort it decides everything.

But what about n log n?

Any sort that learns about the data only from “less or not” comparisons makes in the worst case at least log₂ n! ≈ n log₂ n − 1.44n comparisons: each comparison is a yes or a no, and there are n! permutations. The proof is in the article on the lower bound. Counting sort does not contradict this bound, because it plays a different game. The line count[key] += 1 is a question with 381 possible answers, which the machine answers in one memory access: the cell's address is the answer.

The price is the range of keys. Time and memory are O(n + k), and with k much larger than n the work goes into empty counters. Choose the key “time” in the first scene: there are 347,120,818 seconds from the start of 2015 to the last event in the catalogue, and a counter for each is 18 thousand times more than there are earthquakes. Such a key cannot be sorted by counting. But it can be split into parts.

One digit per pass

Long before computers, punched cards were sorted by a machine that in one pass read one column and dropped the cards into pockets numbered 0 to 9. To order the cards by a multi-digit field, the operator ran the deck through the machine several times, starting with the rightmost, least significant column of the field, and after each pass gathered the pockets in order. Below are sixteen earthquakes of 2025 of magnitude 7 and above, by time of day: four digits, four passes.

Why start with the least significant digit and not the most significant, the way people compare numbers? Switch the order of the passes and look at the result: the deck is ordered only by the last digit read. Each pass lays the deck out anew, and of the previous passes only the order within a pocket is left. So the last pass must be the main one, by the most significant digit.

Without stability the proof falls apart in the second case, and so does the sort itself. Hence the choice of sort for a pass: counting, which is stable, linear and made for digits with few values.

This gives radix sort from the least significant digit, LSD. In a computer it is convenient to take binary digits: a 32-bit number is four bytes, four passes of 256 counters. The radix listing below returns the catalogue sorted by magnitude back to time order: the key is seconds since 2015, four passes of a byte each. The input is almost ordered, since there are only 83 magnitudes and within each the events already go by time, and it has only 69 out-of-order neighbours. After the first pass there are 3089, after the second 9413, after the third 8340, and only after the fourth zero. Radix sort does not care how ordered the input is: the order appears only on the last pass.

The digit width is a free choice. A digit of b bits gives ⌈32/b⌉ passes of 2^b counters: with b = 8, four passes of 256; with b = 16, two of 65,536. Fewer passes means fewer reads of the array, but more counters, and when the counter array no longer fits in the first-level cache, the layout starts missing the cache. A byte is a common choice: 256 counters take a couple of kilobytes and never leave the cache.

Strings: from the most significant character

Strings have different lengths, and they have no least significant digit. But they do have a most significant one, the first character. Lay the strings out into buckets by their first character; within each bucket all strings share the same beginning, and the order between buckets is already right. Lay each bucket out by the second character, and so on, until a bucket has one string left. This is sorting from the most significant digit, MSD, and in effect it builds a trie on the fly: the buckets are its nodes.

Below are the addresses of all 8966 pages of this site from its sitemap. Click the buckets and go down: the sections of the site, then the English versions of pages, the textbooks, the unit converter.

Sorting from the most significant character needed 252,849 looks at a character. Merge sort made 99,160 comparisons and read 1,824,994 characters in them, 7.2 times more. The reason is shared beginnings. To compare /en/utilities/unit-converter/square-centimeter-to-square-mile and …-to-square-millimeter, a comparison reads 60 identical characters, and in the next comparison with a neighbouring address the same 60 again. Radix sort reads each character of each string at most once and stops as soon as a string is alone in its bucket. Reading less is impossible: any sort has to read each string up to the place where it differs from its neighbours.

MSD has a weakness too: at each level it sets up 128 or 256 buckets, even if a bucket holds three strings. So real implementations finish small buckets with insertion sort. A well-known variant without a second array is American flag sort from the paper “Engineering Radix Sort” by Peter McIlroy, Keith Bostic and Douglas McIlroy (1993): there counting sets the bucket boundaries, and the elements are moved to their buckets by cycles right in place. The authors wrote that their string sorts are usually at least twice as fast as a good quicksort.

Code

Counting sort on the whole catalogue. To avoid fractions, the magnitude is read from the text straight into hundredths: “5.36” → 536. The check at the end is that the answer matches a stable merge sort element for element.

Radix sort is counting sort in a loop over digits. First the punched card sorter from the second scene, then the whole catalogue by seconds, a byte per pass:

And strings from the most significant character: the sitemap, the counts of characters read by both sorts, and the most similar neighbours in the answer.

What it costs

For 32-bit numbers d = 4 with byte digits, and radix sort is linear: four counting passes and four layouts, whatever n is. A comparison sort on a million numbers needs about 20 comparisons per element, radix sort eight passes over the array, four counts and four layouts, without a single comparison. A measurement on random 32-bit numbers:

In Go a twenty-line radix sort beats slices.Sort two to two and a half times: 51 ms against 127 on a million numbers, 474 ms against 1150 on ten million. In Python it is the other way round: our radix sort is 3–4.5 times slower than sorted. Each of its steps is a line of the interpreter, while sorted is written in C, and the interpreter eats up the whole gain in the number of operations. That is why libraries that care about speed write radix sort in C. In numpy the stable sort of an integer array up to 16 bits, np.sort(a, kind="stable") for int8, int16 and their unsigned relatives, is radix sort, and for the other types Timsort.

Where it will not do

• The key must be a number or a string of digits. What can be sorted by counting is what turns into a cell number. Negative integers are shifted: for a 32-bit number it is enough to flip the sign bit, and the order of the unsigned numbers matches the order of the signed ones. Floating-point numbers also reduce to integers by a bit trick, flipping the sign bit of positive ones and all bits of negative ones; this is how, for example, DeviceRadixSort in the CUB library for graphics cards sorts them.
• Comparison by an arbitrary function is not available. Records can be radix-sorted by a compound rule “by city, and on ties by date descending” only if the rule is first encoded into a key.
• A second memory is needed. LSD lays out into a second array of the same length. In-place variants exist, such as American flag sort, but they are unstable and so suit MSD, not LSD.
• Small arrays and long keys. Four passes of 256 counters on an array of 50 numbers is 1024 prefix sum additions for the sake of 50 elements. For 64-bit keys there are already eight passes, twice the work, while a comparison sort hardly cares about the length of the key.

Where it is used

Git. Each git object pack comes with an index, and it begins with a fan-out table of 256 numbers: the N-th number is how many objects in the pack have a first name byte no greater than N. These are exactly the prefix sums of a counting sort by the first byte. Further on the index holds the sorted object names, and to find an object git takes its first byte, uses two neighbouring numbers of the table to find the stretch holding all names with this byte, and searches by binary search within it.

Graphics cards. Radix sort splits into independent pieces: each thread counts its part of the histogram, and prefix sums are computed in parallel. So radix sort fits graphics cards well: NVIDIA's CUB library has DeviceRadixSort for this.

Suffix arrays. To find substrings in a long text or genome, the suffixes of the text are sorted. The classic way is doubling: sort the suffixes by their first 1, 2, 4, 8, … characters, where each step is a sort of pairs of already known ranks. The pairs are two-digit numbers, and they are conveniently radix-sorted with two counting passes. That is how the second problem of this article works.

Data with a small range. Exam scores, ages, character codes, grades from 1 to 5, brightness histograms of images: wherever there are few values and many elements, counting is the fastest and simplest way. An example with school leavers' scores is taken apart in the course chapter “The sorting tournament”.

History

Radix sort is older than computers. Herman Hollerith built tabulators for the 1890 census, and by the next census cards had to be sorted, and in 1901 the firm released a sorting machine. IBM card sorters then did exactly one thing for decades: read one column and drop the cards into pockets; the model 82 of 1949 handled 650 cards a minute. Operators sorted multi-column fields from the least significant column to the most significant, pure LSD, with stability provided by the mechanics themselves: cards land in a pocket in the order they arrive.

On computers radix sort at first seemed awkward: how much room should each bucket get, if it is not known in advance how many elements will land in it? In 1954 Harold Seward proposed in a master's thesis first to go through the data and count the bucket sizes, and then lay the elements out directly into their final places in one array. That is counting sort, and its stability made radix sort on a computer as simple as on a card sorter.

Problems

The first is a warm-up with a catch: IP addresses look like strings but must be sorted as numbers. The second is a genome's suffix array by doubling, where each step is a radix sort of pairs.