The constant the notation drops

Once two algorithms have both been placed in $\Theta(n \log n)$, the classification has said everything it is going to say. It has also implied that a further question exists, because two algorithms in the same class are not the same algorithm, and the difference between them is a number.

That number is the constant. If an algorithm’s comparison count is asymptotically $c \cdot n \log_2 n$, then $c$ is what the notation discards, and $c$ is what decides which of two same-class algorithms does less work.

It is not hard to measure. Divide the measured count by $n \log_2 n$ at every size and look at what it settles to.

Where the number comes from #

The fit that grants a class computes this on the way. For a candidate class $f$, the ratio $\text{count}(n) / f(n)$ is computed at every measured size, and the class is granted only if that ratio stays flat. If it stays flat, the value it stays flat at is the constant.

So the constant is not an extra measurement bolted on. It is a by-product of the test, and the same evidence that establishes the class establishes the number.

Measured on random input from n = 32 to n = 4,096:

The spread column is how flat the ratio was — 1.00 would be perfectly flat, and everything here is within 1.41. That flatness is what entitles the middle column to be called a constant rather than a number that happens to be true at one size.

Reading the table #

Several things in it are more informative than the classification.

Merge sort is the comparison champion, and it is not close. At 0.838 it does 48% fewer comparisons than heapsort and 25% fewer than randomised quicksort. Where comparisons are what cost — sorting strings, sorting by a user-supplied comparator, sorting anything where the comparison is a function call — merge sort is the algorithm and the margin is large.

Heapsort is the most expensive thing in the class. This surprises people who know heapsort as the algorithm with the good worst case. Both facts are true: heapsort’s worst case is $\Theta(n \log n)$ with no bad inputs at all, which is a genuinely valuable guarantee, and it pays for that guarantee with a constant nearly twice merge sort’s. The sift-down operation compares a node against both children at every level, and that “both” is most of the factor.

Adding an insertion-sort cutoff makes merge sort worse at comparing. 0.838 goes to 1.059, a 26% increase. Insertion sort is comparison-hungry on the small subarrays it takes over, and the hybrid pays for it. Every production sort implements a cutoff anyway, for reasons that are about memory traffic rather than comparisons — which is exactly the kind of thing a single-count analysis cannot see.

The three quicksorts cluster tightly. 0.995, 1.051, 1.120 — all within 13% of each other on random input. The pivot rule barely matters here, which is worth knowing, because the pivot rule matters enormously on inputs that are not random. First-element pivoting costs 130,816 comparisons on a sorted array of 512 where random pivoting costs 5,490, a factor of 24. The constants on random input say nothing about that, and the distribution does.

What a constant is not #

It is not a running time, and the ranking by constants is not the ranking by speed. Merge sort’s comparison constant is the best in the table and merge sort allocates a buffer the size of the input, which quicksort does not. On real hardware, quicksort’s locality frequently beats merge sort’s comparison economy. Nothing in this table can establish that, and the second count exists because of it.

It is not transferable between cost models. These are comparison constants. The write constants would rank the same algorithms differently — selection sort, which is not even in this table because it is quadratic, does fewer writes than anything here. Every constant is a constant for a named count, and quoting one without naming the count is the same error as quoting a class without naming the input.

It is not stable across input distributions. Merge sort’s constant is 0.838 on random input. On already sorted input its comparison count drops to 2,304 at n = 512, against 3,964 on random, and the fitted constant is exactly 0.500 — one comparison per element per level rather than two, because merging two already-ordered runs exhausts one side and copies the rest without asking. Same algorithm, same class, different number. The table above is a table about random input and says so.

It is not a fundamental property of the algorithm. It is a property of this implementation of the algorithm, under this cost model. A merge sort that compares a[j] < a[i] and one that compares a[i] <= a[j] do the same number of comparisons but differ in stability; a merge sort that checks whether the two halves are already in order does dramatically fewer comparisons on nearly-sorted input and slightly more on random. The constant moves.

The constant is not one number either #

An honest constant needs three qualifiers, and dropping any of them turns it back into folklore.

Which count. The table above is comparison constants. Do the same exercise on writes and merge sort’s number is exactly 1.000 writes per $n \log_2 n$ — one write per element per level, with a spread of 1.00, which is as clean a constant as this site measures — while heapsort’s is 1.792. The ratio between them is close to the comparison ratio, coincidentally, and there was no reason it had to be. Do it on total reads and writes and the ordering shifts again, because merge sort’s buffer copy costs traffic that quicksort never pays. Every count is a different question and every question has its own constant.

Which input. Merge sort’s comparison constant is 0.838 on random input and about 0.49 on sorted input, because merging two already-ordered runs exhausts one side early and skips the rest. Same algorithm, same class, a factor of 1.7 between the two numbers. Any constant quoted without its input distribution is quoting one column of a table and hiding the rest.

Which implementation. The constant is a property of the code, not of the idea. A merge that checks whether the last element of the left run is below the first of the right — a two-line addition that costs one comparison per merge — takes merge sort’s constant on already-sorted input from 0.500 to near zero, and leaves it untouched on random input. The algorithm is still merge sort. The number moved.

This is why the constants on this site are always presented with a range, an input and a link to the source rather than as facts about sorting algorithms in general.

The constant against the floor #

There is one comparison in which the constant becomes more than a relative measure, and it is the most useful thing on this page.

No comparison sort can average fewer than $\log_2(n!)$ comparisons, and $\log_2(n!) \approx n \log_2 n - 1.44n$. So the ideal constant, asymptotically, is 1 — and any algorithm’s measured constant can be read as a distance from optimality rather than as a distance from its competitors.

At n = 256 the floor is 1,684 comparisons. Averaged over sixteen random inputs:

Merge sort is within 2.2% of a bound that no algorithm can beat. That is an extraordinary thing to be able to say about a practical algorithm, and it is not visible from the classification, which merely puts merge sort in the same box as heapsort at 96% above the floor.

This is the floors field’s subject and it is the natural home of the constant. Comparing an algorithm to its competitors identifies which is better among the ones somebody thought of. Comparing it to the floor establishes how much room is left.

What the constants say about the algorithms #

Read as a group rather than as a ranking, the numbers say something about how each algorithm spends its comparisons.

Merge sort spends almost none of them wastefully. Its comparison count is close to the theoretical minimum because merging two sorted runs extracts nearly a full bit of information per comparison: each one determines the next element of the output and nothing is repeated. The decision-tree bound says a perfect algorithm extracts exactly one bit per comparison, and merge sort’s 2.2% gap at n = 256 is how close a practical algorithm gets.

Heapsort spends about half of them establishing things it will discard. Sifting an element down compares it against both children to decide which way to go, and the losing comparison contributes nothing to the final order — it only decides which subtree to descend. That structural waste is the factor of two.

Quicksort spends them on partitions that are not quite balanced. A perfectly balanced partition would give $n \log_2 n$ comparisons and a constant near 1. Random pivots give expected partitions at the 25/75 mark on average rather than 50/50, so the recursion is slightly deeper than optimal, and the measured 0.995 is what that costs. Median-of-three improves the balance and adds comparisons to compute the median, and the measured 1.120 says the second effect wins at these sizes — which is a genuinely surprising result and would not be visible without the number.

Shellsort’s 1.206 is not really a constant at all. Shellsort’s complexity depends on its gap sequence in a way that is still not fully settled theoretically, and the class the fit grants it — $n \log n$, spread 1.41 — is the loosest fit on the site. That looseness is information: it is the fit saying that this algorithm is less well described by a single class than the others, which matches what is known about it.

Why the constants are so rarely quoted #

The obvious question, given how easy the measurement is: why does nobody publish these?

Partly because they are implementation-specific and therefore feel unrigorous. A constant that changes when the inner loop is rewritten is not a theorem, and the culture around algorithm analysis is oriented towards theorems.

Partly because they are published, in the specialist literature, and mostly for the specific case of comparison counts under specific input models — Knuth computes many of them exactly, and the exact asymptotic constant for merge sort’s average comparison count is known. What is rare is not the number but the habit of putting it next to the class as a matter of course.

And partly because a constant invites the question of what it is a constant of, and answering that question honestly means naming the cost model, the input distribution and the implementation. That is three more sentences than “it’s $O(n \log n)$”, and the three sentences are where the actual information is.

What to do with a constant #

Three uses, in increasing order of how much they justify the measurement.

Choosing between same-class algorithms. Where comparisons dominate, merge sort’s 0.838 against heapsort’s 1.613 is decisive, and no amount of thinking about classes would have got there.

Estimating. A constant makes the class into an arithmetic prediction. Merge sort on a million elements: $0.838 \times 10^6 \times 20 \approx 1.7 \times 10^7$ comparisons. That is a number to multiply by a cost per comparison and set against a budget. The class alone offers nothing to multiply.

Detecting that something is wrong. This is the one that pays for itself. If an implementation’s constant is 2.5 where the reference implementation measures 0.84, the class still fits, the curve is still straight, and something is doing three times the work it should. A fitted exponent will not catch that, because a constant factor does not change a slope. The constant is the only thing that will.