Why do production hybrid sorts fall back to insertion sort on subarrays below a small threshold?

## The crossover exists because big-O throws away the constants An `O(n log n)` sort and an `O(n^2)` sort have running times of roughly `a·n·log n` and `b·n^2`. Asymptotic superiority says only that the first eventually wins — it promises nothing at small `n`, where `a` versus `b` decides the race. For insertion sort `b` is about as small as a sorting constant gets: one comparison and one move per inner step, all indices, no allocation, no function-call overhead. For a divide-and-conquer sort `a` carries recursive frames, pivot selection or a merge buffer, and range bookkeeping on every level. Solve `b·n^2 < a·n·log n` for the observed constants and the crossover lands somewhere in the low tens of elements. ## What actually makes the small case fast - **No recursion.** Every recursive level costs a call frame, argument setup and a return, and at the bottom of the recursion tree those levels are the *majority* of all calls — a recursion over `n` elements bottoming out at size 1 makes about `n` leaf calls. Cutting off at 16 removes roughly the bottom four levels of the tree, which is where most of the calls live. - **No scratch memory.** Insertion sort is in-place, `O(1)` auxiliary. A merge step needs a buffer for the slice; allocating or indexing one for 12 elements is pure overhead. - **Cache and prefetch behaviour.** The inner loop touches contiguous slots moving in one direction; a slice of a few dozen elements sits inside a handful of cache lines and typically stays resident for the whole sort of that slice. Partition-based sorts move data from both ends and jump between subranges. - **Branch behaviour.** At the bottom of a recursion, slices are frequently partially ordered already, so the inner loop exits after one or two comparisons and the branch predictor sees a stable pattern. - **Adaptivity for free.** Whatever partial order the surrounding algorithm has already imposed on a slice, insertion sort exploits: its cost is proportional to the remaining inversions, not to the slice length squared. ## The threshold is measured, not derived You cannot compute the cutoff from the recurrence, because the quantities that decide it — call overhead, cache line size, comparison cost for the element type, whether the comparison is inlined — are properties of the implementation and machine, not of the algorithm. The engineering method is to benchmark: build a harness over representative element types and input distributions (random, near-ordered, duplicate-heavy, reversed), sweep the threshold across 4, 8, 16, 32, 64, and look at the whole distribution rather than the mean. Two things usually show up. First, the curve is flat over a wide middle — anything from about 8 to 32 is within noise of optimal, which is why different mature implementations pick different values and all of them are defensible. Second, the best value moves with the element size: large elements make moves expensive and pull the threshold down; cheap-to-compare small elements push it up. ## The fallback is asymptotically free A common worry is that inserting a quadratic algorithm into an `O(n log n)` sort risks quadratic behaviour. It does not, as long as the cutoff `c` is a constant. The recursion produces at most about `n/c` slices of size at most `c`; each costs `O(c^2)`, so the total insertion-sort work is `O((n/c)·c^2) = O(nc)`, which is `O(n)` for constant `c` — strictly less than the `O(n log n)` the rest of the sort already pays. The hybrid's worst case is whatever the outer algorithm's worst case was; the fallback cannot make it worse. There is a second design choice worth knowing: some implementations do not sort each small slice as they reach it, but leave all slices unsorted and run a single insertion-sort pass over the whole sequence at the end. That works because after the outer algorithm stops, every element is within `c` positions of its final place — the sequence is `c`-sorted, so one adaptive pass costs `O(nc)` = `O(n)`. It trades one pass over the whole range for better locality inside the recursion; which wins is, again, a measurement. ## What the interviewer is really testing The answer they are listening for is that you do not treat asymptotic labels as performance predictions. The candidate who says "insertion sort is `O(n^2)`, no serious sort would use it" has confused a growth rate with a cost. The one who says "below the crossover, constants and memory behaviour dominate, and here is how I would find the crossover" has understood what the notation is for.