Where insertion sort actually wins

Open the sorting routine of any standard library and there is a threshold in it. Below some number of elements — 16 in several implementations, 32 in others, 12 in a few — the clever algorithm stops recursing and hands the subarray to insertion sort.

The explanation given is usually some version of: for small n, the constant factors dominate and insertion sort’s are smaller. That is true and it is vague, and the vague version is compatible with a specific claim that people frequently make, which is that below the threshold insertion sort does fewer comparisons.

It does not. Not at sixteen elements, not at eight, not at four.

The measurement #

Mean over sixty random inputs at each size:

“Traffic” is reads plus writes — every element fetched and every element stored.

The comparison columns tell an unambiguous story: merge sort is ahead at four elements and pulls further ahead at every size after that. There is no crossover to find, and a figure looking for one would find nothing.

The traffic columns tell a different story. Insertion sort is ahead at 4, 6, 8 and 12; merge sort is ahead at 16 and everything above. The crossover is between 12 and 16 — which is, satisfyingly, exactly the range where real implementations put their thresholds.

The crossover is a claim about a mean, and the mean hides a band #

Every number in that table is an average over sixty inputs, and averaging is a choice that this site is elsewhere quite rude about. It is worth turning the same rudeness on the headline result.

Counting instead how many of the sixty individual inputs insertion sort wins on traffic:

A negative gap means insertion sort moved less data on the median input.

The mean crosses between 12 and 16. The vote crosses at 16 and it crosses by the narrowest margin available — thirty inputs each way, an exact tie. And the last input on which insertion sort wins is somewhere between 24 and 32: at n = 24 there are still four random arrays out of sixty that it handles with less traffic than merge sort, and only at 32 does merge sort win all sixty.

So the crossover is not a point. It is a band about twelve to thirty-two elements wide, inside which which algorithm is cheaper depends on the particular array, and the threshold a library picks is a decision about where inside that band to stand rather than a discovery of where the lines meet.

That matters for the folklore in a second way. A cutoff of 16 is not “the point at which insertion sort stops winning”; it is the point at which it stops winning more often than not. An implementation with a cutoff of 24 is still winning on one subarray in fifteen, and an implementation with a cutoff of 12 is giving up wins on more than two subarrays in three. Both are defensible, which is why both exist.

The width of the band is also why nobody has settled the argument by measurement. Sixty inputs put the tie at 16; a different generator, a different element distribution, or a different number of trials will move it by a few elements, and the three effects below that the traffic count does not see move it further. A band is the honest shape of this answer and a threshold is the shape an implementation needs, so somebody has to round.

Why the two counts disagree #

Merge sort is extremely good at comparing and comparatively expensive at moving.

Its comparison efficiency is near the theoretical floor: each comparison in a merge determines exactly one output element and is never repeated. Even at n = 4 that efficiency is already showing.

Its traffic is another matter. A merge reads from the source array, writes into a buffer, and then copies the buffer back. Every element is therefore read at least twice and written at least twice per level of recursion, plus the reads charged by the comparisons themselves. At n = 4 that is 25.4 accesses to place four elements.

Insertion sort’s traffic at n = 4 is 17.2. It reads an element, walks backwards shifting until it finds the place, and writes it down. On a nearly-sorted or tiny array the backwards walk is short and the total movement is small. It does more comparing and less carrying.

So which algorithm is cheaper depends on which of those is being charged for, and at small $n$ the two counts give opposite answers. This is the site’s recurring theme in its sharpest form: the counts are exact, they disagree, and the disagreement is not noise.

Why the comparison count was never going to cross #

It is worth seeing why merge sort’s comparison advantage holds even at four elements, because the reason is not an accident of the implementation.

Merge sort at $n = 4$ splits into two pairs, sorts each with one comparison, and merges with at most three — a maximum of five comparisons, averaging 4.7. The information-theoretic floor for four elements is $\lceil\log_2 24\rceil = 5$ in the worst case, so merge sort is at the floor here. It cannot be beaten.

Insertion sort at $n = 4$ averages 5.0. It is above the floor even at this size, because its inner loop rediscovers the position of each element by walking, and the walking repeats comparisons that a merge would have made once.

So the comparison crossover does not exist because merge sort is optimal at every size in this range and insertion sort is not. There is no size small enough for insertion sort to catch up, and there never was going to be.

What insertion sort has instead is a small constant per operation — no recursion, no buffer, no bookkeeping — and that constant lives in the traffic count and in things below the traffic count. The folklore compressed “smaller constants” into “fewer comparisons”, and the two are not the same claim.

What the real reason is #

The traffic count is a better proxy for what hardware charges than the comparison count, and there are three further effects it still does not capture — all of which point the same way.

Recursion has a cost that no array count sees. Merge sort at n = 4 makes several function calls. Each is a stack frame, a few register saves, a branch the processor may not predict. Insertion sort at n = 4 is two nested loops with no calls at all. The instrumented array records nothing about this because nothing touches the array.

The buffer competes for cache. Merge sort’s scratch space is the size of the input. On a small subarray this is trivial, but the buffer is allocated once for the whole sort, so it is a second array of the full size being touched alongside the first, halving the effective cache available at every level.

Branch prediction. Insertion sort’s inner loop on a nearly-sorted subarray exits after one or two iterations, predictably. Merge sort’s inner comparison is essentially a coin flip on random data, and a mispredicted branch costs on the order of fifteen cycles — comparable to a cache miss, and equally invisible in every count on this site.

All three make insertion sort look better than the traffic count already shows, which means the true crossover is at least where the traffic count puts it and probably a little higher. That is consistent with implementations choosing 16 or 32 rather than 12.

What this site can and cannot say about it #

It can say, with exact and reproducible numbers, that the comparison count does not cross. That claim is a refutation of a specific and commonly repeated explanation, and refutation is what finite measurement is good for.

It can say that the traffic count does cross, between 12 and 16, and that this is the count that behaves the way the folklore describes.

It cannot say where the crossover is in time on any particular processor, because this site does not time anything. The three effects above are real and unmeasured here, and each of them moves the threshold. Anyone choosing a cutoff for a real implementation should measure it on the target hardware with the target element type, and the reason to do so is that the answer depends on both.

The figure’s assertions encode exactly this. The generator requires that no comparison crossover exists and that a traffic crossover does. If a future change to either algorithm produced a comparison crossover, the caption would be wrong and the build would stop rather than quietly print a false sentence.

What the hybrid costs #

Since the cutoff makes merge sort worse at comparing, it is worth asking how much.

Plain merge sort’s fitted comparison constant on random input is 0.838. With the cutoff it is 1.059 — a 26% increase, permanently, at every size. The hybrid also does 6.8% more writing.

So the cutoff is a straightforward loss in both counts this site measures well, and it is universally implemented anyway, on the strength of the effects it does not measure. That is a slightly uncomfortable conclusion for a site built on measurement, and it is the same honest limit that the fitting machinery runs into elsewhere: the practitioners are right and the justification is in a quantity the instrument does not reach.

What the instrument does establish is that the justification is not the one usually given. That is a smaller result than settling the question, and it is a real one.

The crossing, three more ways #

The crossing is what the essay is about, so it is worth taking on two more inputs and at more trials before a threshold is read off it.

Few distinct values is the other input worth trying, because a comparison there is much likelier to be an equality and the two algorithms treat that differently.

The last of the four holds everything fixed but the count of runs again, in the other direction, so that the pair brackets the setting the page actually quotes.

Where the threshold should actually come from #

Since this site cannot settle the exact cutoff, it is worth saying what would.

The threshold depends on the ratio between the cost of a comparison and the cost of moving an element, and that ratio depends on what is being sorted. Sorting 32-bit integers, a comparison and a move cost about the same and the traffic count is the right guide. Sorting 200-byte records by value, a move is fifty times a comparison and the threshold should be much lower — possibly zero, because merge sort’s comparison advantage is worth more than its traffic disadvantage almost immediately. Sorting pointers to objects, comparisons chase pointers and become expensive again, pushing the threshold back down.

So there is no single right cutoff, and the 16 or 32 that implementations use is a number tuned for the common case of small scalar elements. A library sorting arbitrary user types with a user comparator is choosing a threshold on behalf of workloads it has never seen, which is why some implementations expose it and most simply pick a defensible middle.

The general form of this is the same as choosing a growth factor for a dynamic array: a constant that no complexity class constrains, chosen by measurement, with different implementations landing in different places for reasons that are visible once the trade is drawn.

The overhead is a shrinking fraction #

The cutoff’s cost is quoted above as a 26% rise in the comparison constant, and the arithmetic behind it says something the single number does not.

A cutoff of $c$ removes the bottom $\log_2 c$ levels of the merge recursion and replaces them with insertion sort on $n/c$ subarrays of $c$ elements each. The merging removed is about $n \log_2 c$ comparisons; the insertion sorting added is about $n c / 4$. So the extra comparisons are proportional to $n c$, and the total is proportional to $n \log_2 n$ — which makes the overhead

$$\frac{\text{extra}}{\text{total}} \;\approx\; \frac{c}{\log_2 n}$$

a falling fraction rather than a constant. At $n = 64$ the denominator is 6 and at $n = 4{,}096$ it is 12, so the overhead over the measured range should roughly halve.

The fitted 1.059 is one constant over that range, which averages the drift rather than showing it. Both statements are true of the same data: the hybrid pays 26% more comparisons than plain merge sort over the sizes measured, and the share it pays falls as the input grows.

That reconciliation matters for the practical question. A fixed cutoff gets cheaper in relative terms the larger the sort, so a library choosing 16 is choosing a number whose cost is worst on the small inputs where the traffic saving is largest and best on the large inputs where it barely registers. The two effects point the same way, and the coincidence is what makes a single constant defensible across the whole range a library has to serve.

It also gives the sizing rule for anybody who wants to choose $c$ deliberately: the overhead is $c/\log_2 n$, so holding it under a stated fraction means $c \le \beta \log_2 n$ — which for a tenth and a million elements is two, and for a quarter and a thousand is two and a half. Every real cutoff is far above that, which says the comparison overhead is not what anybody is optimising, and returns the argument to the traffic count and the three unmeasured effects.

Why this threshold is rightly absolute #

The cutoff is an integer with no $n$ in it, and that is worth defending, because this collection has elsewhere complained about exactly that shape.

A threshold expressed as a bare number is calibrated against a machine and ages as the machine changes. That complaint is right about a gallop threshold or a minimum run length, where the number is standing in for a ratio between two costs.

Here it is not. The cutoff’s job is to catch subarrays below the crossover, and the crossover is a property of the two algorithms measured against each other — the band between twelve and thirty-two elements identified above. That band does not move with $n$: a subarray of sixteen elements is the same problem whether it came from sorting a hundred elements or a billion, and the algorithm cheaper on it is the same either way.

So the parameter is correctly absolute, and it is correctly a small integer. What it is calibrated against is the element type and the relative cost of a comparison against a move, which is the point the previous section makes — and that is a calibration a library performs once for scalars and cannot perform at all for a user-supplied comparator.

The reversed-input surprise #

There is a coda, and it is the strangest measurement on the site.

Merge sort with a cutoff, on reversed input, does not fit $n \log n$ over the range this site normally measures. Fitted from n = 64 to n = 4,096 it fits linear better — a spread of 1.69 against 1.92 — and only when the range is extended to n = 65,536 does the ranking reverse.

The cause is the cutoff. On reversed input the insertion-sort phase is at its worst, costing about $c^2/2$ per subarray for cutoff $c$, and that contributes a term proportional to $n$ which dominates below a few thousand elements. The merging contributes the $n \log n$ term and it is small on reversed input, because merging two runs where every element of one exceeds every element of the other terminates early.

The site’s fitting machinery refused to grant either class, which is correct, and the case became an essay about what measurement cannot establish. It is worth mentioning here because it is the same phenomenon as the crossover: a hybrid algorithm’s cost is a sum of two terms with a crossover between them, and every summary that reports one number is reporting whichever term happened to dominate over the range that was measured.

One of the three effects is now measurable #

The first of the three effects listed above — that recursion costs something no array count sees — stopped being a hand-wave when the space instrument was built.

Merge sort makes 8,192 function calls to sort 4,096 elements. The hybrid, with its cutoff at 16, makes 512. That is a factor of sixteen in call-setup work, exactly, and it is a mechanism rather than an assertion.

It is still not a duration, and this site still does not have one. What it is is the right order of magnitude to account for a crossover that the traffic count only just explains, measured in a quantity that had no counter when this essay was written.