One run, four counts, four answers

Selection sort and bubble sort perform almost exactly the same number of comparisons. At n = 512 on random input the counts are 130,816 and 129,688 — within one percent, and they stay within one percent at every size. By the measure that every introductory course uses to rank sorting algorithms, they are the same algorithm.

They are not the same algorithm. Bubble sort performs 62,563 swaps in that run. Selection sort performs 504.

That is a factor of 124, it is not visible in the comparison count, and if the things being sorted are anything larger than a machine integer it is the number that decides which algorithm was the right one.

The four counts #

Every algorithm here runs against an instrumented array whose primitives tally four things:

• comparisons — how many times two elements were asked which was larger
• swaps — how many times two elements exchanged places
• reads — how many times an element was fetched
• writes — how many times an element was stored

At n = 512 on random input, in full:

Several things in that table are worth more than a glance.

Insertion sort records zero swaps. It is not standing still: it moves a great deal of data — 63,074 writes — but it does so by shifting elements one position with get and set rather than by exchanging pairs. The swap counter is measuring a particular way of moving data, not movement in general, and an algorithm that avoids the primitive shows up as zero.

That is a real limitation of the count and it is worth stating rather than papering over. To compare data movement across algorithms that move data differently, the honest column is writes, not swaps. By that column insertion sort at 63,074 is one of the heaviest movers here, and selection sort at 1,008 is by far the lightest.

Selection sort’s write count is the whole point of the algorithm. $n - 1$ swaps at most, so at most $2(n-1)$ writes, regardless of the input. Nothing else here comes close. Selection sort is the algorithm for the case where writes are catastrophically expensive and reads are cheap — sorting records on media where a write costs orders of magnitude more than a read, which is not the situation most people are in but is exactly the situation the algorithm was designed for.

Merge sort’s reads exceed its writes by nearly three to one. 12,536 against 4,608. Each merge reads both halves and writes the result once, but the comparison primitive charges two reads per comparison, and the copy back from the buffer costs a read and a write each. The asymmetry is structural rather than incidental.

Which count is the right one #

There is no answer to that in general, which is the useful thing to know. There is an answer for each situation, and it comes from what the elements are.

Machine integers, in memory. Comparisons and writes cost about the same — a few cycles each — and both are dominated by whether the data is in cache. Here the comparison count is a reasonable proxy for total work and the ranking it gives is roughly right. This is the case most textbooks silently assume.

Large records moved by value. A comparison touches one field; a write moves the whole record. If a record is 200 bytes and a key is 4, a write is fifty times a comparison and the write column is the one that matters. Selection sort’s 1,008 writes at n = 512 start to look extremely attractive against insertion sort’s 63,074, despite selection sort making twice as many comparisons.

Expensive comparisons. Sorting strings by a locale-aware collation, or sorting objects by a computed key, or sorting anything where the comparison is a function call into user code. Now a comparison may cost hundreds of times a write, and the comparison column is not merely a proxy — it is the answer, and everything else is noise. This is why the standard library sorts of most languages work hard to minimise comparisons specifically, and why the information-theoretic floor on comparisons is a bound anyone in this situation genuinely cares about.

Data on disk or across a network. None of these counts is the right one. What matters is the number of blocks transferred, which is a different quantity again, and which the cache model is a small-scale analogue of.

The pattern is that the choice of cost model determines the answer, the choice is a modelling decision rather than a measurement, and it is almost always made implicitly. A benchmark that reports “algorithm A is better” has chosen a cost model — usually by choosing what to sort — and the choice is rarely stated.

The counts rank differently, and it is not a small effect #

Take the eight algorithms in the table and rank them by each count.

By comparisons, best to worst: merge with cutoff, merge, quicksort, Shellsort, heapsort, insertion, bubble, selection.

By writes, best to worst: selection, merge, quicksort, merge with cutoff, Shellsort, heapsort, insertion, bubble.

Selection sort goes from last place to first. That is not a marginal reordering caused by measurement noise — it is a move across the entire field, produced by changing which exact, deterministic, reproducible number is being looked at.

The same effect appears within a single algorithm’s design decisions. Merge sort with an insertion cutoff performs 4,794 comparisons where plain merge sort performs 3,964: the hybrid does 21% more comparing. It also does 6.8% more writing. On this measure the cutoff is a straightforward loss, and yet every production sorting routine implements one, for reasons that turn out to have nothing to do with either count.

A case where the counts disagree about which algorithm is broken #

The clearest demonstration is an input that most comparisons never use: an array with only a handful of distinct values. Sorting a million records by a status field with eight possible values is an entirely ordinary thing to want to do, and it is where several respectable algorithms come apart.

At n = 512 with eight distinct values, the comparison counts are:

Merge sort barely notices. Shellsort gets slightly faster. Every quicksort variant on the site gets roughly four times slower, and the fitted class moves from $n \log n$ to $n^2$ — which the site’s machinery detects and refuses to paper over, so none of these algorithms carries a declared class on this input.

The reason is that a two-way partition around a pivot equal to many other elements puts all those equal elements on one side. The recursion is unbalanced not because the pivot was unlucky but because the data has few distinct values, and choosing the pivot better — median of three, at random, any of it — does not help at all. Randomising the pivot defends against an adversarial arrangement of the input, and few-distinct-values is not an arrangement. It is a property of the values themselves, and no pivot rule can escape it.

The fix is a three-way partition, which puts elements equal to the pivot in a middle band and recurses on neither side of it. That is what production quicksorts do, and it costs comparisons on ordinary input to buy safety on this one — a trade that is invisible to anyone who only ever measures random arrays.

The two counts, four ways #

The disagreement between the two counts is the claim, so the pair is drawn again at another size and on two more inputs.

Both of those hold the input fixed, and the input is what a count is most sensitive to — far more so than the size, which moves both counters together. The two plates below hold the size at five hundred and twelve and change the order the elements arrive in.

Reversed is the other end of that axis and the worst case for the algorithm the previous plate flattered, which makes the pair the sharpest version of the comparison available.

What none of these counts can see #

Ordered by how much of the truth they capture, the counts form a ladder — and the top rung is not on it.

Comparisons capture the information-theoretic work. Writes capture the data movement. Reads capture the total traffic. And all three are blind to where the accesses go, which on real hardware is most of the cost.

Merge sort and heapsort are both $\Theta(n \log n)$. Merge sort does about half the comparisons. But the interesting number is neither: it is that merge sort makes 49% of its accesses to the next element or the same one, and heapsort makes 14%. Heapsort’s whole method is jumping between a node and its children at indices $2i+1$ and $2i+2$, which for large heaps are nowhere near each other in memory, and no amount of counting comparisons reveals that.

This is why the site carries a fifth quantity that is not in the table above — the complete access trace, which becomes a modelled miss count when replayed through a cache. That count is genuinely independent of the four here, and the site asserts that it is: if the miss count ever became predictable from the comparison count, the second quantity would be carrying no information and the assertion would fail the build.

The same test applied to the swap column gives the complementary answer: swaps predict nothing that writes do not, since every swap is two writes, and the column is retained because it distinguishes exchanging from shifting rather than because it measures a separate resource.

Two properties that no count sees at all #

Two further things distinguish sorting algorithms and neither is a number.

Stability. A stable sort preserves the relative order of elements that compare equal. Merge sort as written here is stable; heapsort and quicksort are not. Stability decides whether sorting by one key and then by another gives a sensible result, which is how most multi-key sorting is done in practice. It costs nothing in comparisons and is invisible in every column above.

Auxiliary space. Merge sort needs a buffer the size of the input. Heapsort, insertion sort, selection sort and quicksort’s partition need a constant amount. That is a factor-of-n difference in memory, it appears in none of the four counts, and it is frequently the constraint that decides the choice. The site does not currently measure it, which is an honest gap: an in-place sort and an out-of-place one with identical counts are different algorithms and nothing here says so.

Both belong on the list of reasons that “which sorting algorithm is best” is not a question with a number for an answer.

What a good comparison looks like #

If the counts disagree and there is no universally right one, comparisons between algorithms are not impossible. They just have to say what they are about.

A defensible statement looks like: merge sort performs 0.838 · n log₂ n comparisons on random input, against heapsort’s 1.613 — measured from n = 32 to n = 4,096, averaged over sixteen seeds. Every part of that is checkable, the cost model is named, the range is named, and the sample is named.

An indefensible statement looks like: merge sort is faster than heapsort. It might be true on some data on some machine, and nothing in it says which, so there is no way to find out whether it holds anywhere else.

This site tries to make only the first kind of statement. Where an essay says one algorithm does less work than another, the work is named. Where it says one is faster, something has been measured that entitles it to the word — and given that nothing here is timed, that word is used very sparingly indeed.

The counts are not independent, and the identity says something #

Four columns look like four degrees of freedom and they are not. Three of them are tied together by an exact identity, and working it out turns the table into a description of how each algorithm is written.

Every read in these runs comes from one of two places: a comparison, which fetches its operands, or a swap, which fetches the two elements it is about to exchange. Every write comes from a swap or a shift. So

$$\text{reads} \;=\; c \cdot \text{comparisons} \;+\; \text{writes}$$

where $c$ is the number of array elements a comparison fetches — two if it compares two positions of the array, one if it compares a position against a value the algorithm is already holding.

Checked against the table, at $n = 512$, it closes exactly on five of the eight rows:

Not approximately. To the unit, on every row.

And the two rows with $c = 1$ are the two insertion-based algorithms, which is not a coincidence: insertion sort lifts the element being placed into a local variable and then compares that held value against array positions as it shifts them along. One array read per comparison, because the other operand is not in the array any more. Shellsort is insertion sort at several gap sizes and inherits the property exactly.

So the identity is a fingerprint of an implementation detail. A reader who had only the four counts and none of the code could recover, from arithmetic alone, which algorithms hold an operand in a register — and that detail is one of the standard hand-optimisations, usually described as saving a memory access and here visible as a coefficient.

The two rows where it does not close are the more interesting ones.

Quicksort with median-of-three leaves a residual of 1,188 reads over $c = 1$. That number is exactly divisible by three, and three is how many elements the median-of-three rule samples per partition — so the residual is 396 partition calls at three reads each, and the identity closes once the pivot selection is accounted for. The extra reads are not comparisons and not swaps; they are the algorithm looking at candidates before deciding what to compare.

Merge sort with a cutoff sits between the two coefficients, because it is literally between the two algorithms: the merges compare two array positions and the insertion-sorted runs compare against a held key, so its reads are consistent with a mixture and with no single $c$.

The general point is worth more than the arithmetic. A set of counters can look like several independent measurements and be two measurements plus bookkeeping, and the way to find out is to try to predict one column from the others. Where the prediction closes, the extra column is carrying no information and is a convenience. Where it fails — as it does for the modelled miss count, which no combination of these four predicts — the extra column is a genuinely new quantity, and that failure is the reason it was added.

The one thing that survives all of it #

Amid all this relativity there is a fixed point, and it is worth ending on because it is the reason the comparison count keeps its privileged position despite everything above.

The comparison count is the only one of the four with a proved floor. No comparison sort averages fewer than $\log_2(n!)$ comparisons, ever, for any input distribution, by any technique anyone will ever invent. There is no corresponding theorem about writes, or reads, or swaps: an algorithm that performs zero writes is conceivable if it is allowed to return a permutation rather than rearrange the array, and the write count therefore has no interesting lower bound at all.

So the comparison count is not merely one arbitrary choice among four. It is the count that connects to a theorem, and that is why measuring how close each algorithm gets to its floor is a more informative exercise than measuring the others. It is still not the running time, and it is still not the right count for every situation — but it is the one where the question “could anything do better?” has an answer.

There are now six #

This essay reports four counts. The site has since added two more — modelled cache misses, and peak auxiliary space — and the pattern it describes holds across all six rather than being a curiosity of the original four.

Ranking the ten sorts by each of the six and counting the pairs ordered differently, comparisons and peak space disagree about 91% of pairs, which is close to a reversal. The full table is a separate essay, and its conclusion is this one’s, arrived at with a larger vocabulary: there is no ranking of sorting algorithms, there are six, and choosing between them is a statement about the data.