The exchange rate nobody wrote down

This collection has made the same promise three times and never kept it.

“If the elements being sorted are machine integers, selection sort’s write economy is worth very little. If they are large records that must be physically moved, it is worth a great deal, and the ranking by comparisons is the wrong ranking entirely.” — counting instead of timing.

“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.” — one run, four counts, four answers.

“Sorting 200-byte strings, a single comparison walks up to 200 bytes, and the comparison count is then a count of variable-cost operations dressed up as a count of atoms.” — what O notation does not say.

Three statements, all correct, none of them a number. This page is the number.

It is worth asking why a promise gets made three times and kept none. The answer is not laziness; it is that keeping it requires a decision the essays were each in the middle of avoiding. Combining two counts into one number needs an exchange rate between them, and an exchange rate is a claim about somebody’s hardware and somebody’s data — exactly the kind of claim this collection is careful not to make. So each essay noted the effect, declined the arithmetic, and moved on. What follows is the arithmetic done with the rate stated as a parameter rather than assumed, which is the form the earlier essays could have used and did not.

The model, stated so it can be argued with #

A cost in bytes needs a rule and the rule is a choice. This one:

A read or a write moves the whole record. A comparison touches the key only.

So for a run with $c$ comparisons, $r$ reads and $w$ writes, the bytes are $(w + r - 2c)\cdot\text{record} + c\cdot\text{key}$ — the $2c$ subtracted because this site’s counter charges a comparison as two reads, and those two reads are reads of keys rather than of records.

That subtraction is not a detail. The first version of this arithmetic charged $r + w$ at the record rate and reported selection sort as the heaviest mover on the site, which is the exact opposite of the effect the model exists to show: selection sort makes 130,816 comparisons at this size, each counted as two reads, and charging those at 200 bytes apiece buries everything else. An implementation sorting large records compares keys and moves records, and the two rates have to be applied to the two different things.

With the subtraction, the quantity that matters becomes visible:

Selection sort moves 2,016 elements. Nothing else on the site moves fewer, and it is the only algorithm here whose movement is $O(n)$ rather than $O(n \log n)$ or worse. That is its entire and only virtue, it has been visible in this collection’s counts since the first plate, and until now nothing has said what it is worth.

There is a general point in that first-version failure and it is worth extracting, because it is a mistake this collection is well placed to make repeatedly. A counting convention chosen for one purpose becomes a modelling assumption when the counts are combined. Charging a comparison as two reads is a perfectly good convention for measuring memory traffic in an integer sort — the reads are real, and an implementation that cached one operand would perform fewer, which the convention says openly. It stops being a convention and becomes a claim the moment those reads are priced at a record’s width, because in the world where a record is 200 bytes an implementation would not be reading records to compare them.

Where each pair changes places #

Bytes are linear in the record size, so two algorithms cross at most once and the crossing is one division. If $m$ is elements moved and $c$ is comparisons, algorithm A beats B exactly when

$$(m_A - m_B)\cdot\text{record} < (c_B - c_A)\cdot\text{key}$$

which is a single value of the record size, positive or nowhere. Against selection sort at 512 elements and an eight-byte key:

Read that column downwards and it is a schedule. Below nine bytes a record, selection sort is beaten by insertion sort. Above 276 bytes, it beats everything measured here. Between those, it overtakes its rivals one at a time in an order that has nothing to do with their complexity classes — heapsort first, then merge sort, then two algorithms that beat both of them at every size.

“It depends on the record size” is usually said as though the answer were a range. It is a point, and the point is computable from counts the site already had.

The crossing points also say something about which algorithms are worth having in a library. Quicksort’s median-of-three variant and shell sort sit at the top of the table for every record size drawn, so nothing in this range dislodges them, and their crossings against selection sort are beyond the largest record anybody sorts by value. Merge sort and heapsort are dislodged at 141 and 67 bytes, which are ordinary record sizes — a struct with a handful of fields. The two algorithms this collection uses as its well-behaved reference points are the two whose ranking is least robust to the exchange rate, which is not a fact anybody would guess from their comparison counts.

What the model gets wrong, in the one place it can be checked #

The rule charges a comparison a fixed number of bytes. For a machine integer that is right. For a string it is not, and the error is not a constant.

Comparing two strings walks them until they differ, so the cost is the length of their common prefix plus one. How long that is depends on how many keys share a prefix, and how many keys share a prefix depends on how many keys there are.

That is measurable directly. Sort keys of a fixed length with a comparator that reports how far it had to walk, and sweep the number of keys while holding the length constant:

The key length is twenty characters at every row. The only thing changing is how many of them there are, and the cost of a comparison rises by 83% over a 256-fold range — which is a logarithm, and which means the byte cost of a comparison sort on string keys is not in the same class as its comparison count. $\Theta(n\log n)$ comparisons at $\Theta(\log n)$ characters each is $\Theta(n\log^2 n)$ characters.

Two things about that table are worth separating, because only one of them is surprising. That a string comparison costs more than an integer comparison is obvious and was already stated three essays ago. That its cost grows with the number of keys is not, and it is what breaks the model rather than merely qualifying it: a fixed rate can be wrong and still be a rate, and a rate that is a function of $n$ is not a rate at all. It is a term, and it belongs in the class rather than in the constant.

Why the exchange rate is a modelling decision and not a measurement #

The bytes on the hero plate are computed rather than counted, and it is worth being precise about what that means for their status.

This site’s counters are exact. Comparisons, reads, writes, cache misses, random bits, block transfers — each is an integer produced by an instrumented run, identical on every machine. A byte count is those integers multiplied by two constants somebody chose, and the choosing is where the content is.

That puts it in the same category as the cache model’s line size, the external-memory model’s $B$ and $M$, and the weighting that two pivots and what they cost found inside a published analysis — a parameter that must be stated before the conclusion means anything. The plate states both parameters, and this is why.

The useful thing a stated rate buys is not a number. It is that the conclusion can be recomputed at somebody else’s rate. A reader whose records are forty bytes and whose keys are two can take the two columns of counts above and get their own crossings, from a division. A reader given only “selection sort is good for large records” has to take it or leave it.

What a real system does with this, which is not what the plate suggests #

The measurement says selection sort wins above 276 bytes a record. No production sorting routine has ever chosen selection sort for large records, and understanding why is more useful than the crossing.

The reason is that the choice on the plate is a choice between sorting the records where they lie, and nobody does that. The standard move is to sort an array of pointers — or of key-and-index pairs — and permute the records once at the end. Then every algorithm’s movement cost falls to the pointer width, the comparison cost stays whatever the key comparison costs, and the ranking snaps back to the four-byte column at the top of the plate for every record size.

So the honest reading is that the plate measures a regime that a competent implementation escapes, and the escape has a price: an extra array of $n$ pointers, an extra indirection on every comparison — which is a scattered memory access, and therefore expensive in a unit where an algorithm looks measures rather than in this one — and a final permutation whose cost the external-memory field has already priced.

That does not make the exchange rate uninteresting. It relocates what it decides. The record size does not choose between sorting algorithms; it chooses whether to sort the records at all, and the crossing points on this page are where that second decision turns. A reader whose records are twelve bytes should sort them directly and a reader whose records are five hundred should sort pointers, and the arithmetic that says so is the same arithmetic.

Where the model breaks that this page does not measure #

Three ways, and the second is the largest.

A record move is not proportional to its size. Moving 512 bytes is not 128 times moving four, because a machine moves memory in blocks and a large contiguous copy runs at a rate a small one cannot reach. The model’s linearity is the assumption that makes the crossings computable, and it is the assumption that is least true at the top of the range.

Sorting pointers is the real alternative and it is not on the plate. Nobody sorts 512-byte records by moving them; they sort an array of pointers or indices and permute the records once at the end. That changes every number here — the movement becomes eight bytes an element and the permutation at the end is a separate cost, which is exactly the permutation problem the external-memory field measures. The whole reason large-record sorting is interesting is a technique this page’s model cannot express.

And the comparison’s cost has a second dependence. The characters-per-comparison measurement above is on random strings over a two-letter alphabet. Real keys share prefixes for structural reasons — file paths, URLs, sorted identifiers — and the sharing is far heavier than randomness gives. The direction is against the comparison-heavy algorithms and the magnitude is unmeasured.

The one algorithm the exchange rate was invented for #

Selection sort is the case this page keeps returning to, and it is worth saying exactly what makes it the interesting one rather than merely the extreme one.

Its movement is $n-1$ swaps — at most one per position, and only when the position is wrong. That is not a small constant on an $n\log n$ quantity; it is a different quantity, linear where every other algorithm here is linearithmic or quadratic. So the ratio between selection sort’s movement and anything else’s grows with $n$, and the record size at which it overtakes a rival falls as $n$ rises.

That is a genuine asymptotic statement rather than a fact about 512 elements, and it is the strongest form of the argument this page makes: at a large enough $n$, selection sort beats merge sort in bytes moved at any record size larger than the key. What stops that being a recommendation is the comparison column, which is quadratic and which the exchange rate is multiplying by a constant — so the crossing exists and the record size at which it happens is falling, while the absolute cost of both is rising quadratically for one of them.

Working the two against each other gives the honest conclusion. Selection sort’s advantage is real, it is in one column, and it is bought with a column whose growth is worse. An algorithm can be optimal in one resource and inadmissible overall, and this is the site’s clearest example — which is why the collection has reported its two columns separately for as long as it has had them.

What this adds to the count somebody chose #

The count somebody chose measured six quantities for every sort, ranked the algorithms by each, and found that comparisons and peak space disagree about 91% of all pairs. Its conclusion was that there is no ranking of sorting algorithms, there are six, and choosing between them is a statement about the data.

This page is the next step and it is a slightly uncomfortable one. The six can be combined, and the combination is a ranking — of a machine. Given a record size and a key size, the seven algorithms here have a total order, and it is computable from the counts already taken. The disagreement between counters does not go away; it is resolved by a parameter, and the parameter is a property of the elements rather than of the algorithms.

Two things follow that are worth separating.

A ranking exists once the exchange rate is fixed, which is more than the earlier essay concluded and is not a contradiction of it: that essay’s point was that no ranking exists without one, and this page supplies one and gets an ordering.

And the exchange rate is not a fact. It is two numbers about the caller’s data, and a paper, a benchmark or a recommendation that does not carry them has fixed them silently. That is the same complaint the earlier essay makes about a weighted combination inside a published analysis, and it is the reason this page prints its rule at the top rather than at the bottom.

Where this ladder goes from here: the count that came from the engine #

Every count on this site is described as exact, reproducible to the last digit, and identical on every machine that has ever built the page. That claim is the foundation of the whole collection and it is worth auditing rather than repeating.

It is not quite true, and the leak is in a place nobody would look. Several measurements here call the language’s own sorting routine — an edge sort inside a spanning-tree algorithm, the run-formation pass of an external merge sort — and count the comparisons it makes through the comparator. The standard requires the result to be sorted and stable, and says nothing whatever about how, so those numbers are facts about the engine executing the build rather than about sorting.

The interesting part is not the leak but what a measurement of it shows: that routine is adaptive in a way nothing in its specification mentions, its comparison count on random input comes within about one per cent of the information floor, and it varies by a factor of ten across input kinds where a fixed merge sort varies by a factor of two. All of that is measurable through the comparator, none of it is guaranteed, and every number on this site that passes through it inherits the whole of it.