Algorithms & Data Structures
the bound is a claim, and it is checkable
What the machine does

Where insertion sort actually wins

Every production sorting routine falls back to insertion sort on small subarrays, and the usual explanation is that below some threshold it does fewer comparisons. Measured, it does not — not at sixteen elements, not at eight, not at four. The crossover is real and it is entirely in memory traffic, which is a distinction the usual telling loses.
13 min read 6 figures Two counts, two rankingsMeasured, not asserted

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.

Where insertion sort actually wins — and it is not in the comparisonsMean over 60 random inputs at each size, both counts on one pair of axes. Insertion sort performs more comparisons than Merge sort at every size measured, including n = 4: the dashed pair never cross. The solid pair — total reads and writes — do cross, between n = 12 and n = 16. The familiar advice to fall back to insertion sort on small subarrays is right, and the reason is memory traffic rather than comparisons, which is a distinction the usual telling of it loses.481632641281010010³10⁴noperations (mean of 60 runs)Insertion trafficMerge trafficInsertion cmpMerge cmptraffic crossessolid: reads + writes · dashed: comparisonstraffic crosses between n = 12 and 16; comparisons never do
Fig. 1 Insertion sort against merge sort, both counts on one pair of axes, averaged over sixty random inputs at each size. The dashed lines are comparisons and they never cross — insertion sort makes more at every size measured, including n = 4. The solid lines are total reads and writes, and those do cross, between n = 12 and n = 16.

The measurement

Mean over sixty random inputs at each size:

n insertion cmp merge cmp insertion traffic merge traffic
4 5.0 4.7 17.2 25.4
6 11.6 10.1 37.8 52.2
8 19.1 15.8 61.0 79.5
12 42.5 30.4 132.3 148.8
16 74.5 45.6 228.8 219.2
24 161.4 82.2 490.5 388.4
32 278.2 121.1 841.5 562.3
64 1,073.0 304.8 3,227.3 1,377.5

“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.

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 nn 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=4n = 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 ⌈log⁡224⌉=5\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=4n = 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.

Comparisons used, as a multiple of the floor, n = 256The information-theoretic floor at n = 256 is 1,684 comparisons: a binary decision tree with 256! leaves cannot be shallower than that. The bar is what each algorithm averaged over 16 random inputs, divided by the floor. Merge sort comes within 2% of it; Selection sort uses 19 times as many.the floorMerge sort1.02×Quicksort, first1.23×Quicksort, random1.24×Merge sort + cutoff1.29×Quicksort, median-31.32×Shellsort1.45×Heapsort1.96×Insertion sort9.69×Bubble sort19.26×Selection sort19.38×floor = log₂(256!) = 1,684 comparisonsmean of 16 runs, against a proved bound
Fig. 2 The floor argument at a larger size, where it is drawn rather than argued. Merge sort at 1.02 times the floor is doing very nearly the theoretical minimum of comparing; insertion sort at 9.69 is doing ten times as much. The gap does not close as n shrinks — it is smallest at n = 4, and it does not reach zero.

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.

Comparisons and swaps at n = 512Selection sort performs the most comparisons of any algorithm here and among the fewest swaps — it never moves an element it does not have to. Ordering these algorithms by comparisons and ordering them by swaps gives two different orders, which is why the question "how many operations" needs the operation named before it has an answer.comparisonsswapsInsertion sort63,071 / 0Selection sort130,816 / 504Bubble sort129,688 / 62,563Merge sort3,964 / 0Heapsort7,653 / 4,170Quicksort5,049 / 2,380n = 512, random inputcounted in the same run
Fig. 3 The same disagreement at a larger size, across more algorithms. At n = 512 the comparison ranking and the swap ranking differ, and both differ from the write ranking. A hybrid algorithm is a decision about which of these to optimise at which scale, and the decision only makes sense once the count has been named.

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.

Same class, different constantsEvery algorithm here fits n log n on random input. The bar is the fitted constant — comparisons divided by n log n — and the largest is 1.9 times the smallest. That factor is invisible in the notation and is the whole of what distinguishes these algorithms by this measure.comparisons ÷ n log nMerge sort0.855Merge sort with a cutoff0.992Quicksort, random pivot1.018Quicksort, first-element1.082Quicksort, median of three1.117Shellsort1.246Heapsort1.649all of these fit n log n1.9× between best and worst
Fig. 4 The cost of the cutoff, in the constant. Plain merge sort sits at 0.838 comparisons per n log₂ n and the hybrid at 1.059. Every production sort pays that 26% for a benefit that lives outside the comparison count entirely.

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.

Comparisons against modelled cache misses, n = 2048One point per algorithm, both axes logarithmic. If the comparison count determined the memory behaviour the points would fall on a line, and they do not: Merge sort and Quicksort, median-3 and Merge + cutoff sit at least two places apart in the two rankings. Cache model: fully associative · 64 lines × 8 elements · LRU. The vertical axis is a modelled miss count, not a time.10⁵10⁶10³10⁴10⁵comparisonscache misses (modelled)Insertion sortSelection sortBubble sortMerge sortHeapsortQuicksort, firstQuicksort, median-3Quicksort, randomShellsortMerge + cutofffully associative · 64 lines × 8 elements · LRUa modelled count, not a time
Fig. 5 Why the element type changes the answer. Comparisons on one axis and modelled memory behaviour on the other. Where an algorithm sits on this plot is fixed; how much each axis costs is a property of the data being sorted, and it is the thing a library cannot know in advance.

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 nlog⁡nn \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 c2/2c^2/2 per subarray for cutoff cc, and that contributes a term proportional to nn which dominates below a few thousand elements. The merging contributes the nlog⁡nn \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.

Comparison counts against n, reversed inputMeasured counts on logarithmic axes, where a power law is a straight line and its exponent is the slope. The quadratic algorithms rise at twice the gradient of the linearithmic ones, and the vertical gaps between the parallel lines are the constants the notation discards.10010³10⁴10³10⁴10⁵10⁶10⁷10⁸10⁹ncomparisonsMergeMergeInsertiona power law is a straight line herecomparisons, counted exactly
Fig. 6 The coda drawn. On reversed input the hybrid’s line is not parallel to plain merge sort’s over the left of this range — the insertion-sort term dominates and the line looks linear. Insertion sort’s own line above shows why that term is so large: reversed input is its catastrophe case, and the cutoff hands it exactly that case n/c times.

Where this goes next

10⁵10⁶10³10⁴10⁵comparisonscache misses (modelled)Insertion sortSelection sortBubble sortMerge sortHeapsortQuicksort, firstQuicksort, median-3Quicksort, randomShellsortMerge + cutofffully associative · 64 lines × 8 elements · LRUa modelled count, not a time The count is not the time An operation count is exact, machine-independent, and not a running time. The gap between them is mostly memory, and it is large enough to reorder the rankings. This site carries a second count — modelled cache misses from the same runs — and asserts that the two disagree, because if they agreed the second one would carry no information. comparisonsswapsInsertion sort63,071 / 0Selection sort130,816 / 504Bubble sort129,688 / 62,563Merge sort3,964 / 0Heapsort7,653 / 4,170Quicksort5,049 / 2,380n = 512, random inputcounted in the same run One run, four counts, four answers The question “how many operations” has no answer until the operation is named. Selection sort makes more comparisons than any other algorithm here and fewer writes than almost all of them; bubble sort matches its comparisons and does 124 times the swapping. The ranking depends entirely on which count is chosen, and the choice needs justifying. -50%-40%-30%-20%-10%0%10%20%2561,0244,09616,384α = 0.5α = 0.8α = 0.9α = 0.95table size (slots)measured minus formula, relativemean of 6 fills per pointgreen band: within 5% of the formula A limit is not a prediction Measured from n = 64 to n = 4,096, this site's hybrid merge sort fits a linear class better than n log n. Measured out to n = 65,536, the ranking reverses. Nothing changed but the range — and this is not a flaw in the method, it is the method finding the exact place where measurement stops being able to help.