The count that came from somewhere else

Counting instead of timing is this collection’s founding claim and it is stated without hedging: a stopwatch measures the laptop it runs on and a counter measures the algorithm, so every number here is exact, reproducible to the last digit, and identical on every machine that has ever built this page.

A claim that strong deserves an audit rather than a repetition. This is one, and it finds a leak.

The audit is worth doing for a reason beyond tidiness. A collection that says every number here is exact and turns out to have exceptions has two problems, and the second is worse than the first: the exceptions themselves, and the fact that a blanket claim gives a reader no way to tell which numbers to check. Naming the exceptions converts a claim that is nearly true into a claim that is true with a stated boundary, which is the form every other claim on this site takes.

Where the leak is #

Two measurements on this site call the language’s sorting routine and count what it does.

The first is a spanning-tree algorithm. Kruskal’s method sorts every edge by weight and then walks them in order, and the constant that is practically constant reports the split: on a sparse graph of 2,048 vertices and 6,144 edges, 11,143 union–find pointer hops against 42,385 comparisons spent in the sort. The essay’s argument is that the component the famous theorem is about is a quarter of the component nobody discusses, and the argument is right.

The number is not a property of sorting. It is what the engine executing the build did to those 6,144 edges, and a different engine would give a different integer.

The second is an external merge sort’s run-formation pass, which sorts each memory-sized chunk before writing it out, and whose comparison count feeds every figure in the external-memory field that reports comparisons rather than transfers. Those figures’ transfer counts are unaffected — the transfers are counted by this site’s own block model — so the leak there is narrower, and it is real.

Two numbers, in two fields, that are exact for this build and are not the same on another engine. That is a smaller leak than it could be and it is not nothing.

What the specification actually requires #

The language standard requires the result of a sort to be sorted, and — since 2019 — requires it to be stable. It says nothing about the algorithm, nothing about the number of comparisons, and nothing about the order in which the comparator is called.

So the honest description of that 42,385 is: the number of comparisons this engine’s sorting routine performed on this input. It is exact. It is reproducible on this engine. It is not machine-independent, and machine-independence is the property the whole collection is built on.

The gap between “reproducible” and “specified” is the interesting one, and it is the same gap a limit is not a prediction is about in a different direction. A number can be perfectly repeatable and still be a fact about an implementation.

What the measurement shows about the routine #

Having found the leak, the interesting thing is what closing the instrument around it reveals. Three properties, none of which is guaranteed and all of which are measurable.

It is adaptive, sharply. On already-sorted input it makes exactly $n - 1$ comparisons — 4,095 at four thousand elements, 16,383 at sixteen thousand — which is one pass confirming the order and nothing else. On reversed input it makes the same, because it detects a descending run and reverses it. A fixed merge sort makes 24,576 and 114,688 on the same inputs.

On random input it is within one per cent of the information floor. The floor under every comparison sort computes $\log_2(n!)$ exactly, which at 4,096 elements is 43,250. The engine’s routine makes 43,810 — a factor of 1.013 above a bound nothing can get under. That is a remarkable number and it is not an accident: the routine is a merge sort with a galloping mode, and a merge sort’s comparison count is close to the floor by construction.

And it exploits existing order in proportion. Nearly sorted input — sorted with one element in twenty displaced — gives 10,806 comparisons against a merge sort’s 24,845, a saving of 57%, where fully sorted input saves 83%. So the routine’s advantage is graded rather than a special case for two extreme inputs, which is what distinguishes a genuinely adaptive method from one with a sorted-input check bolted on the front. When galloping pays measures the mechanism that produces that gradation, on an implementation written here rather than on the engine’s.

And its behaviour on duplicates is in between. Eight distinct values across four thousand elements gives 27,561 comparisons against a merge sort’s 42,338, so the routine finds and exploits the runs that duplicates produce without collapsing to a linear pass.

The last column is the audit’s real finding. A number that varies by a factor of six depending on the input, in a routine whose specification promises nothing about it, is not a number to quote beside one this site computed.

There is a fourth property worth naming because it is the one that makes the routine safe to depend on in a different sense. It is deterministic: the same array gives the same comparison count on every run in this engine, with no seed and no timing dependence. A routine with a randomised pivot would not, and a count taken from one would be a sample rather than a measurement. So the numbers that leak are at least reproducible within the build, which is why the leak is a portability problem rather than a reproducibility one — and those are different failures with different consequences for a page that promises both.

Why the floor is not a bound on any single input #

A reader looking at the table will notice that the merge sort’s 24,576 comparisons on sorted input is below the floor of 43,250, and that needs saying rather than leaving.

The floor is $\log_2(n!)$ and it is a bound on the worst case, and equivalently on the average over all inputs, for a deterministic comparison sort. It is not a bound on any particular input. A specific permutation can be identified with far fewer comparisons — the identity permutation with $n-1$ of them — and a sort that is fast on that input is slow on some other one, because the total number of leaves in its decision tree is still $n!$.

So there is no contradiction, and the shape of the trade is exact: an algorithm that spends fewer comparisons on sorted input must spend more on something else. The engine’s routine spends 43,810 on random input against the merge sort’s 43,976 — very slightly fewer, not more — which means its adaptivity is essentially free on this family of inputs and is paid for on inputs neither of them was measured on.

That is the same accounting the floor under every comparison sort sets out, and the pair of columns here is a measurement of it: one algorithm sits near the floor everywhere and the other dives below it where it can.

What an audit like this can and cannot conclude #

Three things it establishes and two it does not.

Established: the leak exists and is bounded. Two measurements in two fields pass through an unspecified routine. Every other count on this site — comparisons in the sorting field, cells in the tables field, transfers in the external-memory field, arc examinations in the graph field, random bits, branch mispredictions — comes from this collection’s own instrumented structures and is machine-independent.

Established: the numbers are exact for this build. They are not estimates or samples. A reader running the same engine gets the same integers.

Established: the routine measured is very good. Within 1.3% of the floor on random input and linear on sorted input is close to the best behaviour a comparison sort can have, so nothing here is a complaint about the routine.

Not established: how far the numbers would move on another engine. Every major engine’s sorting routine is a variant of the same adaptive merge sort, so the random-input figure would move by a few per cent and the sorted-input figure would not move at all. That is an expectation rather than a measurement, and this site cannot take the measurement because it runs on one engine.

And not established: whether anything else leaks. The audit found these two by looking for calls to the routine. A leak of a different shape — a hash iteration order, a floating-point rounding, a locale-dependent comparison — would not have been found this way, and no systematic search has been made.

How the leak was found, and how it would be found again #

The two calls were found by looking for them, and it is worth saying what “looking” consisted of, because the method generalises and the alternative methods do not.

Reading the counts would not have found it. 42,385 comparisons for sorting 6,144 edges is 6.9 per edge, which is within a whisker of $\log_2 6144 = 12.6$ halved — exactly what a good sort should do — so the number looks correct and is correct. Nothing about it is anomalous.

Fitting a class would not have found it. The count fits $E \log E$ across a sweep, because the routine really is an $O(n \log n)$ sort. A curve that fits its claimed class is the outcome this site treats as evidence, and here it is evidence of the right thing about the wrong subject.

Only an inventory found it: enumerating every place a count is produced and asking, for each, which code performed the operation being counted. That is a boring exercise with no cleverness in it, it is the only thing that works, and it is the kind of thing that gets done once and then not again as a collection grows.

The general form is worth stating because it is a rule about instruments rather than about sorting. A counter reports what its wrapper saw, and it reports nothing about what the wrapper enclosed. A comparator handed to somebody else’s routine counts comparisons faithfully and says nothing about who made them, and the resulting number carries no mark of its provenance. That is a property of every counting instrument in this collection and it is the reason an inventory is the only audit that works.

What to do about it #

The repair is not to stop using the routine. It is to say which numbers came from it, which this page does and the two essays involved now can.

There is a real alternative and it has a real cost. Both leaking measurements could call a sort written here — the counts would become machine-independent, and they would become worse: a fixed merge sort on 6,144 edges makes more comparisons than the engine’s routine does, so the spanning-tree essay’s split between sorting and union–find would shift, in the direction of making the sort look more dominant than it is on any real machine.

That is an uncomfortable trade and it is the honest one. A machine-independent number that describes an implementation nobody would ship is not obviously better than an engine-dependent number that describes what actually happens. The collection’s position elsewhere is consistent with the second: it measures the algorithms people run, refuses to convert counts into durations, and states the model. Naming the model here is the same move.

The other three places a number can come from #

Setting the leak in a taxonomy makes it smaller and more useful, because there turn out to be four ways a count on this site can be produced and only one of them is fully machine-independent.

Counted by this collection’s own instruments. An array that tallies its reads, a graph that tallies its arc examinations, a table that tallies its cells, a block model that tallies its transfers. Exact, machine-independent, and the overwhelming majority.

Computed in closed form. $\log_2(n!)$, a bound’s predicted value, a formula’s expectation. Exact and machine-independent by construction, and the thing measurements are checked against — which is the pairing the floor under every comparison sort is built on.

Counted through a boundary. This page. Exact for the build, dependent on what is on the other side of the boundary.

Modelled with a stated parameter. A cache miss at a stated line size, a byte cost at a stated record size, a transfer at a stated $B$. Exact given the parameter, and the parameter is on the plate — which is the discipline this whole collection runs on and the one the third category should join.

The fourth category is instructive because nobody worries about it. A modelled number carries its parameter visibly, so a reader knows exactly what to vary. A number counted through a boundary carries nothing, which is why it needed an audit to find and why the repair is to make it look more like the fourth kind: state what it was measured against, on the plate, and let the reader decide what it is worth.

What this rung adds to the counting field #

The field’s first rung says a counter measures the algorithm and a stopwatch measures the machine. That is right, and this page is its qualification: a counter measures the algorithm it is wrapped around, and a call into somebody else’s code is a hole in the wrapper.

That generalises past sorting. Any measurement of a program that calls a library is a measurement of that library’s version; any measurement that depends on a collection’s iteration order depends on its implementation; any measurement involving floating-point accumulation depends on the order of operations the compiler chose. Each is a place where “exact and machine-independent” becomes “exact and implementation-dependent”, and the distinction is invisible in the number.

The counting field’s discipline handles it the way it handles every other model parameter: name it on the plate. The cache model prints its line size, the external-memory model prints its $B$ and $M$, the branch predictor prints its table size, and a count that came from somewhere else should say where.

What the audit did not change #

It is worth ending on what stays true, since a page that finds a crack in a foundation is easy to over-read.

Every complexity class this site has granted is granted on measurements taken by its own instruments. Every fit, every ratio test, every refusal to grant a class, every floor computed in closed form: none of those passes through a boundary. The two leaks are in reported component counts inside two essays — a figure quoting how much of an algorithm’s work goes into a sorting step — and neither of them is load-bearing for a claim about a class.

So the finding is a qualification of a sentence rather than a retraction of a result, and the qualification is small and precise: two numbers are exact for this engine and would move on another. Both are named here, both are in essays that can now say so, and the boundary they crossed is the only one the inventory found.

That is a better outcome than the audit deserved to produce, and the reason to write it down anyway is the one this collection gives for every check it runs. An assertion nobody has tried to break proves nothing about the thing it asserts; it proves something about the person who wrote it.

Where this ladder goes from here: the count of a run that never happened #

Everything measured on this ladder is a count from a run — an execution that took place, over an input that existed. That is the collection’s greatest strength and it has an edge nobody has looked over.

A count from a run is a count of one run. For the deterministic algorithms here that is enough, because the same input gives the same count. For the randomised ones it is not: a quicksort with a random pivot has a comparison count that is a random variable, and every plate on this site reports one draw from it. Expected is not average makes the case that the distribution rather than the mean is what matters, and it makes it by sampling — running many times and looking at the spread.

The unasked question is whether the distribution can be computed rather than sampled. For a randomised quicksort on distinct keys the answer is yes: the probability that two elements are ever compared is exactly $2/(|i-j|+1)$, the expected count is a sum of those, and the variance has a closed form. So there is an exact answer available for a quantity this site currently estimates, the estimate can be checked against it, and the check would say how many runs a sampled distribution actually needs before its shape is trustworthy — which is a number this collection quotes nowhere and relies on everywhere.