The comparison that is not one comparison

Every algorithm published on this site has been written against a counted array, and that array charges one for comparing two elements. The charge is exact and it is the foundation of everything here: the comparison count of a sort on a given input is an integer, the same integer on every machine, and it is the number the fits in fitting a class to measurements are fitted to.

For numbers the charge is also correct. Comparing 41,772 with 8,109 is one operation on any processor that has ever been built.

For strings it is a modelling assumption, and it is the same assumption the external-memory field was built to remove one level up. Comparing algorithmic with algorithms costs ten character examinations before it can answer. Comparing algorithmic with zebra costs one. The first is not ten times more work than the second in some vague sense — it is exactly ten units of the thing the machine actually does, against exactly one, and a counter that reports both as “1” has thrown away a factor of ten it had in its hands.

What the old counter has been charging #

lib/count.js exposes four primitives — get, set, cmp, swap — and every sort on this site is written against them. cmp(i, j) increments a counter and returns an ordering. That is the right instrument for the question the foundation asked, which was how many decisions does this algorithm make, and the answer to that question is genuinely machine-independent in a way a duration never is.

The new field asks a different question, and it needs a different instrument — a counted comparator rather than a counted container:

const c = new TextCounter();
c.cmp("algorithmic", "algorithms");
// c.charCmp === 10
// c.elemCmp === 1

The structural difference is forced by the subject. A sorting algorithm’s input is an array it permutes; a string algorithm’s input is a text it reads, and the operation worth counting is the character examination rather than the access. So TextCounter counts two things at once: elemCmp, which is the old unit and is exactly what the sorting essays already publish, and charCmp, which is new.

Both are exact. Both are machine-independent. They are not the same number and they do not rank the same algorithms in the same order, which is the third instance on this site of the pattern one run, two counts named — comparisons against cache misses, comparisons against block transfers, and now comparisons against characters.

The measurement that makes the field necessary #

The opening figure is one experiment with one independent variable, and it was chosen because it isolates the effect completely.

Take 512 keys, each eight random characters over an alphabet of eight. Sort them with merge sort. Then repeat with the same 512 keys, with the same eight random characters, each prefixed by four identical characters. Then eight. Then sixteen, twenty-four, thirty-two.

Nothing about the ordering changes. Prefixing every key with the same characters cannot reorder them: if key $i$ sorted before key $j$ before, it sorts before it now, because the comparison that decided it is still decided at the same position, just shifted right. Merge sort’s comparison count depends only on the permutation, so it must be identical at every point.

It is. 3,955 element comparisons, six times over.

The character count over the same six runs is 7,849, then 23,669, 39,489, 71,129, 102,769, 134,409. That is a factor of 17.1 in the cost the machine pays, across a sweep in which the count every published bound on this site is stated in did not move by one.

The mechanism is not subtle and the numbers say it plainly. Characters per comparison across the six runs: 1.98, 5.98, 9.98, 17.98, 25.98, 33.98. Each is the imposed prefix plus 1.98 — the prefix, which every comparison must walk before it can learn anything, plus whatever the random tails cost, which is the same in all six. The instrument is recovering the construction exactly, which is the check that it is measuring what it was pointed at.

Why “sorts in $n \log n$ comparisons” stops being a complete sentence #

Merge sort’s guarantee is $\Theta(n \log n)$ comparisons. It is true here, it is true of every run above, and it describes the flat line.

What the machine pays is $\Theta(n \log n \cdot L)$ character examinations, where $L$ is roughly the length of the prefix two keys share before they differ. And $L$ is not a property of the algorithm. It is a property of the data, it can be made arbitrarily large without changing a single decision the algorithm takes, and no amount of care in choosing a sorting algorithm affects it at all.

That is a genuinely different situation from the ones this site has met before. The constant that the notation drops is a property of an algorithm — quicksort’s is smaller than heapsort’s and that is a fact about quicksort. This factor belongs to the input, and the algorithm cannot see it.

The factor is not fixed, even when nothing is imposed #

The experiment above imposes a shared prefix, which is a clean way to isolate the effect and an artificial one. The obvious objection is that real keys do not come with a designer’s prefix bolted on.

They come with something else, and the something else grows.

With 64 keys of eight random symbols, a comparison costs 1.54 characters on average. With 2,048 of them it costs 2.28. Nothing was imposed; the keys are drawn from the same distribution at both sizes. What changed is that there are more of them, so more pairs happen to agree on their first character, and some on their first two.

The slopes on logarithmic axes are 1.207 for the element count and 1.321 for the character count. They are not parallel, and the gap between them is a slowly growing logarithm rather than a constant.

A first version of this figure asserted that the two lines were parallel and failed. The assertion was the thing that was wrong: parallel is what happens when the shared prefix is imposed and fixed, and unimposed keys do not behave that way. It is recorded in the generator, because a measurement that disagrees with an expectation is worth more than a measurement that confirms one, and the site’s own rule is that the assertion has to be able to fail.

The algorithm that does not compare #

The honest comparison for a comparison sort is not another comparison sort. It is an algorithm that does not compare at all.

A most-significant-digit radix sort buckets the keys on their first character, then buckets each bucket on its second, and so on until every bucket holds one key. It never asks whether one key is less than another. What it reads is each key’s distinguishing prefix: the characters that had to be looked at before that key was separated from every other one.

On the 512-key sweep it reads 1,933 characters at a shared prefix of zero and 18,317 at a shared prefix of 32. It also pays for the prefix — it must read those characters to bucket on them — but it pays for each key’s copy once, where the comparison sort pays for it once per comparison that key takes part in, which is about $\log_2 n$ times.

At a shared prefix of 24 the two numbers are 102,769 and 14,221. The ratio is 7.2, it is about $\log_2 512 \approx 9$ discounted by the tails, and it is what re-reading the same prefix nine times costs.

Two more settings of the same experiment say which of its two numbers is the one that moves, and the answer is not the one the bound is written in. Lengthen the tails, quadruple the keys, widen the prefixes: the element comparison count is fixed by the permutation at every point on every one of those axes, and the character count moves by more than an order of magnitude.

What this does to the floor #

The floor under every comparison sort says that no algorithm sorting by pairwise comparison can average fewer than $\log_2(n!)$ comparisons. For 512 keys that is 3,398, and merge sort’s 3,955 sits 16% above it.

The floor is untouched by anything in this essay, and that is the point worth being careful about. It is a bound on comparisons, the decision-tree argument that produces it counts leaves rather than characters, and a radix sort does not violate it — a radix sort is not a comparison sort, it makes zero comparisons, and $\log_2(n!) \le 0$ is not a claim anybody made.

What the character count adds is a second floor that lives beside it. Sorting $n$ strings requires reading enough of each one to distinguish it from its neighbours in the output, so the total distinguishing prefix length is a lower bound on characters read, and it is a bound the radix sort very nearly meets. The comparison sort meets neither: it is 16% above the comparison floor and a factor of $\log n$ above the character one.

The two floors are floors on different resources of the same job, which is the shape the space field already put on the page, and it is the shape the entropy floor takes later in this field.

The character floor is also the more interesting of the two, because unlike $\log_2(n!)$ it is not computable from $n$ alone. It depends on the keys: 512 keys that differ in their first character have a total distinguishing prefix length of 512, and 512 keys that agree for the first thirty-two characters have one of at least 16,896. So there is no single number to quote, and the honest form of the bound is a function of the input rather than of its size — which is unusual enough on this site to be worth flagging, because every other floor here has been quotable as soon as $n$ was known.

What a word list actually costs #

The random-key experiments are clean and they understate the effect, because random keys are the case where shared prefixes are rarest.

Sorting 512 keys built from ten stems and twelve suffixes — the shape of an actual word list — costs 3,969 element comparisons and 20,666 character examinations. That is 5.21 characters per comparison against the random case’s 1.98, on keys of comparable length, and the difference is entirely that a vocabulary has beginnings that repeat.

The radix sort reads 4,433 characters on the same keys, through 244 buckets. The ratio is 4.7, and it is smaller than the imposed-prefix case’s 7.2 for a reason worth stating: the word list’s shared prefixes are shorter than 24 characters, so there is less re-reading to save.

What has to be said about the old measurements #

Nothing published before this phase is wrong, and it is worth being exact about why.

Every sort measured on this site was measured on integers. INPUTS.random, INPUTS.fewUnique, INPUTS.nearlySorted and the rest produce numbers, cmp on two numbers is one operation, and the counts are exact counts of what the machine does. The bounds fitted to them hold.

What the character counter shows is that those measurements have a precondition that was never written down, in the same way that the bound with a precondition found one hiding inside a graph algorithm’s guarantee. The precondition is that a comparison costs one, and it is satisfied by every input the site had used and by essentially none of the inputs a sort is actually called on in a program — where the keys are names, paths, identifiers, URLs, or anything else assembled out of characters.

That is not a small footnote. It means the ranking in the sort the library ships is a ranking of comparison counts, and a library sorting strings is optimising a different quantity — which is why real string sorts are three-way radix quicksorts rather than the general-purpose hybrid, and why they are a separate function in every standard library that has one.

The character floor, once the keys have a distribution #

The character floor is described above as not quotable from $n$ alone, and that is right and is not the end of it: given a distribution over the keys, it is quotable, and the expression explains every ratio in this essay.

Take $n$ keys drawn at random over an alphabet of $\sigma$ symbols. Two such keys agree on their first character with probability $1/\sigma$, on their first two with probability $\sigma^{-2}$, and a key is distinguished from all the others once its prefix is unique — which happens at about $\log_\sigma n$ characters. So

$$\text{distinguishing prefix total} \;\approx\; n \log_\sigma n$$

and that is the floor a radix sort nearly meets. A comparison sort makes $n\log_2 n$ comparisons and each walks the shared prefix, so it spends about $n \log_2 n \cdot \log_\sigma n$ characters. The ratio between them is $\log_2 n$ — the number of comparisons each key takes part in, which is exactly the number of times its prefix gets re-read.

At $n = 512$ that predicts a factor of nine and the measurement is 7.2, the difference being that the tails are not walked in full. At $n = 2{,}048$ it predicts eleven. The gap between the two floors is a logarithm and it widens with the input, which is the same statement the non-parallel slopes make and is now an expression rather than an observation.

It also explains the alphabet’s effect without a second measurement. Narrowing $\sigma$ raises $\log_\sigma n$, which raises both floors in proportion — so a two-symbol alphabet makes everything more expensive and leaves the ratio between the two sorts alone. The measurements bear that out: the two-symbol plate costs six characters per comparison where the eight-symbol one costs two, and the radix sort’s advantage is the same logarithm in both.

The algorithm that takes both floors #

The essay sets a comparison sort against a radix sort and real string sorts are neither, which is worth naming because the hybrid is the resolution rather than a compromise.

A three-way radix quicksort partitions on a single character at the current depth — less than, equal to, greater than — and recurses into the equal bucket at depth plus one and into the other two at the same depth. It compares, so it is not a radix sort; it compares one character at a time and never re-examines a character it has already partitioned on, so it does not re-read shared prefixes.

Its character count is therefore close to the distinguishing-prefix floor rather than a logarithm above it, and it keeps a comparison sort’s access pattern — a partition sweeps rather than scattering into $\sigma$ buckets, which is the cost the last section of this essay says a radix sort pays and this counter cannot see.

That is why it is what every standard library with a dedicated string sort actually ships, and why the pair of floors in this essay is the right frame for reading the choice: the two floors are on different resources, the two pure algorithms each reach one of them, and the hybrid is the one that gets near both.

What this counter cannot see #

Three things, and each one is a boundary rather than a defect.

It does not know how long a character is. Every count here treats one character as one unit, which is right for a fixed-width encoding and wrong for a variable-width one, where a comparison may have to decode before it can compare. That is a real cost and this instrument charges nothing for it.

It does not see where the characters are. A string comparison walks two pointers through memory, and whether those two regions are in cache is exactly the question the machine field exists to ask. A radix sort’s access pattern is very different from a comparison sort’s — it scatters into buckets rather than sweeping — and the character count says nothing about that. On short keys the scatter can cost more than the re-reading saves, which is the honest reason comparison sorts are still the default.

It says nothing about which algorithm is faster. This is the same disclaimer the count is not the time makes about every counter here, and it is not weaker for being repeated. A character comparison is a byte load and a branch; the two counts in the opening figure differ by 17 and the durations will not, because the prefix walk is a sequential read of two cache lines and the branch predictor learns it immediately.

What the counter does is make a cost visible that was previously invisible and unbounded. The next essays in this field take the same unit to a different question — not how many characters a sort examines, but how few a search can get away with, which turns out to be fewer than the text has.