The sort that makes none of them

One run, four counts, four answers made the case that the question “how many operations” has no answer until the operation is named, and named four: comparisons, swaps, reads, writes. Every plate since has reported at least one of them, and the first is the one nearly all of them report.

There is a sort that makes none of the first. Radix sort distributes keys by one digit at a time, from the least significant up, and after the last digit the array is sorted. It never asks which of two keys is larger. Counted by the instrument this collection was built around, it makes zero comparisons — not few, not a constant factor fewer, none — and the floor under every comparison sort says nothing about it, because the floor is an argument about how much one comparison can reveal and it makes no comparisons.

That sounds like a way past a limit and it is not one. This page counts what it does instead.

How it is counted here #

The instrument needs one addition and it is worth naming, because a sort that makes no comparisons is a sort the counted array was not designed to watch.

Counting instead of timing is the array that increments a tally each time it is read, written, compared or swapped. Radix sort reads every key twice a pass, writes it once into a scratch array and once back, and compares nothing — so three of the four counters work unchanged and the fourth reports zero honestly.

The scratch array is the part that needed care. A radix pass writes each key to a position given by its digit’s running counter, and if those writes are not in the trace then the one thing this page is about — where the writes land — is invisible. So the scratch array’s addresses go into the same trace as the input’s, offset by $n$, and the cache model sees the whole of what a pass touches rather than half of it. A version that traced only the input would have reported radix sort as almost perfectly sequential, which is the shape of mistake the count that came from somewhere else is about: a count that is exact about what it measures and silent about what it does not.

The four counts, side by side #

Three numbers and three different answers.

In comparisons, radix sort wins by not playing. Merge sort makes 965,752, within 1.2% of the 954,037 the floor demands, which is as close as any method gets. Radix sort makes none. Every plate that reports comparisons reports a zero for it, and a ranking by comparisons puts it first by an infinite margin — which is as clear a demonstration as there is that a ranking is a statement about its unit.

In data moved, radix sort wins by a factor of five. 786,432 reads and writes against merge sort’s 4,028,656. Four passes over the array, each reading every key twice and writing it twice, against merge sort’s seventeen levels of recursion each copying the array in and out.

In cache misses, it loses by a factor of three. 369,510 against merge sort’s 122,779 — and that is the count that decides, because this is a sort of a large array and a miss is worth hundreds of the other operations.

Why it misses #

The reason is in the shape of the pass rather than in its size. A pass counts how many keys have each digit value, turns the counts into starting positions, and then walks the array writing each key to its digit’s position. With 8-bit digits there are 256 such positions, each advancing independently, so a pass writes to 256 separate places at once. A cache of 64 lines cannot hold 256 streams, so nearly every write is a miss.

Merge sort’s writes, by contrast, are two streams merged into one — three places, all advancing forward. Where an algorithm looks is the argument that the access pattern is the thing to measure rather than the operation count, and radix sort is the cleanest case on the collection: fewer operations, more misses, and the difference is entirely in how many places at once.

That also says which dial to turn, and turning it is not simple.

The data moved falls monotonically with the digit — it is $2 \cdot \lceil w/b \rceil$ passes over the array, so doubling the digit halves it. The misses do not. They fall to 329,867 at four-bit digits, rise to 369,510 at eight, and fall again to 196,608 at sixteen.

The non-monotonicity is the two effects crossing. Fewer passes means fewer chances to miss; more streams means more of each pass’s writes miss. At four bits there are sixteen streams and they fit in the cache, so a pass is nearly sequential and costs little; at eight bits there are 256 and none of them fit, so every write misses and there are still four passes; at sixteen bits every write misses too, but there are only two passes.

The misses per element do not move with the array’s size at all: 5.03, 5.64 and 3.00 at 65,536 keys against 5.01, 5.65 and 3.00 at 4,096. That is what makes the previous plate a statement about the method rather than about one experiment. A pass’s miss rate is decided by how many streams it writes to against how many the cache holds, and neither of those is $n$.

And the sixteen-bit setting’s counters are 65,536 words — as many as the keys. That is the space this sort spends and no comparison sort does, and it is what makes the bottom of the miss curve unreachable in practice: a sort whose counter array is the size of its input has stopped being a cheap way to avoid comparisons.

The term that is not there #

The two lines have different shapes and the difference is the whole of what the floor is about.

A comparison sort’s count has a $\log n$ in it because $\log_2 n!$ is how many bits it takes to name one of $n!$ orderings and a comparison supplies one bit. Radix sort’s has no such term: it makes $\lceil w/b \rceil$ passes over $n$ keys whatever $n$ is, so its work is $2n \lceil w/b \rceil$ and its line is straight.

The $\log n$ has been replaced by $w$, the key’s width, and that is the trade rather than a saving. Sorting $n$ distinct keys requires them to be distinguishable, so $w \ge \log_2 n$ — there is no such thing as a million distinct 8-bit keys. The two costs are therefore comparable by construction, and the reason radix sort looks better here is that 32-bit keys are wider than $\log_2 65{,}536 = 16$ bits: the sort is paying for sixteen bits of key that carry no information about this particular input.

The floor moves when the question does made the general point that a lower bound belongs to the question rather than to any algorithm. This is the sharper form: a lower bound belongs to a model, and the comparison model’s floor binds every algorithm that only compares and no algorithm that does anything else. A sort that reads a key’s bits is not cheating; it is answering a different question, about keys that have bits, and the floor for that question is a different floor.

Both settings give a straight line and the gap between them is a constant, which is the point: the digit width is a constant factor on radix sort’s work and the key width is the term. Changing the digit moves the line up and down; changing $n$ moves along it; and only changing the key’s width changes its slope, which it does not, because the slope is one.

What it gives up #

Two things, and both are preconditions rather than costs.

The keys must have digits. Every comparison sort on this collection works on anything with a total order — strings, records, objects with a comparator — and learns about its input only through that comparator, which is what the adversary who knows the seed exploits and what makes the floor argument possible at all. Radix sort must be able to take a key apart. A sort of user objects by a caller-supplied comparator cannot be a radix sort, whatever the counts say.

And the width must be known. The passes are $\lceil w/b \rceil$ and $w$ has to be decided before the first pass. Sorting 32-bit keys with a 16-bit width fails: the array comes back sorted by its low sixteen bits, which is not sorted, and the check at the end of every run on this collection catches it. A comparison sort has no such parameter, and the fact that radix sort has one is why it sits in library code for integers and nowhere else.

There is a third property, and it goes the other way. Radix sort is stable, necessarily and for free: each pass distributes stably and the stability of the earlier passes is what makes the later ones correct. The order equal keys keep measured what stability costs the sorts that do not have it — $n$ words of tag and between 0.05 and 2.4 times their comparisons — and radix sort is the one method here where it is not a choice.

That is not a rhetorical point. A plate ranking sorts by comparisons cannot contain radix sort, and a plate that contained it would be a plate whose scale was set by the algorithms that do compare. The methods that share a counter are the methods that can be drawn together, and a collection that measures by counting operations has a boundary at exactly the point where an algorithm stops performing them.

What this says about the counters #

The six counts the count somebody chose measured rank ten sorting algorithms ten different ways, and the argument there was that there is no ranking, only six. Radix sort adds a stronger case: a method can score zero on the count that every other method is compared by, and the zero means it is outside the comparison rather than ahead of it.

That is a general hazard with a counter, and it is worth stating in its general form. A count measures the operations an algorithm performs; a method that performs none of them reports zero; and a zero in a column looks like a win. The repair is the one already in use everywhere here — report several counts, and name the model each floor is stated in — and the reason the repair matters is that the single most quoted fact about sorting, the $n \log n$ floor, is true of the model and not of the problem.

Where it is actually used, and where it is not #

The counts above explain a distribution of practice that would otherwise look arbitrary.

Integer keys in a column store: radix. A column of 32-bit identifiers is exactly the case — the keys have digits, the width is known, the array is large enough that four passes over it is cheaper than seventeen levels of merge, and the stability is wanted because the column is being sorted alongside others. Database sorts of this shape are radix sorts and have been for decades.

Anything with a caller-supplied comparator: not radix. A library’s general sort cannot take a key apart, and every library’s general sort is therefore a comparison sort. That is not a performance decision; it is the only thing the interface allows, which is why the sort the library ships measures four comparison sorts and no fourth family.

Short strings: sometimes. A string is a sequence of digits and a most-significant-digit radix sort over it is a real method, used for suffix sorting and for text indexes. The pass count is then the longest key rather than a fixed width, which is a different arithmetic and one this page does not draw.

The dividing line is the one the counts draw, and it is a line about the interface rather than about the cost: a sort is a candidate for a radix sort exactly when the key’s width is known and small against $\log_2 n$, and it is a candidate for nothing else when the key is only comparable. Neither condition has anything to do with which is faster, and a benchmark comparing the two is comparing methods that are not available to the same caller.

What is not measured here #

One key distribution and one width. The keys are 32-bit values from a multiplicative sequence, near-uniform over their range. Keys clustered in a narrow range leave the high digits constant, and a radix sort that noticed could skip those passes; none here does.

No most-significant-digit variant. This is the least-significant-digit sort, which is the stable one and the one whose pass count is fixed. An MSD radix sort recurses on buckets, stops early on small ones, and has a completely different access pattern; it is not measured.

One cache. Sixty-four lines of eight elements, fully associative, LRU, as everywhere in this collection. The miss counts are a model, and the crossing between four-bit and sixteen-bit digits depends on it — a larger cache holds more streams and moves the bottom of the curve to a wider digit.

Counters counted as words, not as a working set. The 256 counters of an 8-bit radix are four lines and are resident throughout; the 65,536 of a 16-bit radix are a thousand lines and are not. That difference is in the miss counts and not in the space column, which reports words.

The floor is for distinct keys. $\log_2 n!$ counts orderings of distinguishable things, and the floor when the values repeat measured how far it overstates when they do not. Every key here is distinct, so the comparison of merge sort’s 965,752 against 954,037 is the fair one.

Counters, not a full accounting of space. The 8-bit radix holds 256 counters and an $n$-word scratch array, so its peak auxiliary space is $n + 256$ — the same order as merge sort’s $n$ buffer, and measuring what an algorithm keeps is the argument that this axis has to be counted rather than assumed. It is counted here and it is not what separates the two.

And nothing is timed. A pass of a radix sort is a tight loop with no branch on data, and a comparison sort’s inner loop is a branch the processor must predict — which the branch the machine guesses measured and which no count on this page reports.

Still open: the sort that chooses its own radix #

The digit width on this page is a constant chosen before the sort runs, and the plate against it has a shape — data moved falling, misses rising then falling, counters exploding — that has a best setting for every combination of $n$, $w$ and the cache. Nothing here finds it, and a real implementation has to.

The interesting version is the one that does not have to be told. The number of streams a pass can afford is the cache’s capacity in lines, which a cache-oblivious method may not ask for; but the number of distinct values actually present in a digit is something the counting pass measures for free, and a digit whose counts are concentrated in a few buckets is a digit that could have been wider.

The measurement that follows sweeps $n$, the key width and the cache size, finds the digit width minimising total misses at each point, and asks two things: whether that width is predicted by the cache’s capacity in lines — the obvious rule, one stream a line — and whether a sort that widened its digit whenever the previous pass’s counts were concentrated lands near it without being told the cache size at all.