Why does introsort finish small subranges with insertion sort instead of recursing further?

## The shape of introsort Introsort ("introspective sort") is not one algorithm but three glued together, each covering a weakness of the others: 1. **Quicksort** does the bulk of the work — fast on average, in-place, cache-friendly. 2. **A depth limit with a heapsort fallback** caps the worst case: if recursion goes deeper than a preset budget, the remaining subrange is finished by heapsort, which is `O(n log n)` in the worst case. 3. **An insertion-sort base case** handles short subranges instead of recursing all the way down to size 1. This question is about part 3, which is the piece that looks wrong at first glance: insertion sort is the `O(n^2)` algorithm everyone is taught to avoid, and here it sits inside a sort chosen for speed. ## Big-O is a statement about growth, not about cost `O(n^2)` and `O(n log n)` describe how running time *scales* as `n` grows without bound. They deliberately discard constant factors and lower-order terms. Two algorithms with those labels have running times of roughly `c1 * n^2` and `c2 * n log n`; the asymptotically better one wins only once `n` is large enough for the growth difference to overcome the ratio `c1/c2`. Below that crossover the constants decide, and nothing in the notation tells you where the crossover is — you measure it. For sorting, the crossover between insertion sort and a partitioning sort is small but not tiny: measured cutoffs in production sorts cluster around 16 to 32 elements, and the exact value is tuned per implementation and hardware. ## Why insertion sort specifically Insertion sort's inner loop is about as cheap as a sorting step gets: compare the current element with its left neighbour, shift, repeat. There is no recursion, no split-point selection, no bookkeeping of subrange boundaries, no function-call setup per subproblem, and memory access walks a short contiguous stretch in one direction. On a 12-element range that is a handful of compares and moves. It also has a property no other elementary sort has: it is **adaptive**. On input that is already nearly ordered, each element travels only a short distance, and the algorithm degrades to roughly linear work. That matters because after quicksort has partitioned down to small ranges, each range is already *positionally* correct relative to the others; within a range, real data is often partly ordered too. Selection sort, by contrast, always performs about `n^2/2` comparisons regardless of the input, so swapping it in would give up the adaptivity for nothing. ## Why the quadratic term does not leak into the total The worry a candidate should be able to dismiss out loud: "if you run an `O(n^2)` sort inside, isn't the whole thing `O(n^2)`?" No — because the cutoff `k` is a **constant**, not a fraction of `n`. Each base case handles at most `k` elements and therefore costs at most about `k^2/2` operations. There are about `n/k` such ranges, so the total base-case work is about `n*k/2`, which is `O(nk)` — linear in `n` for fixed `k`. The recursion above the base cases still contributes `O(n log n)`; the cutoff actually *removes* the bottom levels of the recursion tree, which are the levels with the most calls and the least useful work per call. Raise `k` too far, though, and the `n*k/2` term stops being negligible relative to `n log n`; that is the ceiling that keeps real cutoffs in the tens rather than the hundreds. ## The one-final-pass variant A well-known variant stops the recursion at ranges below `k` and simply **leaves them unsorted**, then runs a single insertion pass over the entire array at the end. This is correct because after the recursion stops, every element is within `k-1` positions of its final place: the partitioning has already separated the ranges from each other. Insertion sort on an array where nothing moves more than `k-1` slots does `O(nk)` work — the same bound — but as one long sequential sweep instead of thousands of short calls, which is friendlier to instruction and memory prefetching. ## What the base case does *not* do Two mistakes to avoid. First, the cutoff has nothing to do with introsort's worst-case guarantee — that comes entirely from the depth limit and the heapsort fallback. Removing the cutoff makes introsort slower, not asymptotically worse. Second, insertion sort being stable does **not** make introsort stable: the partitioning above it reorders equal elements freely, and the fallback is unstable too. A stable base case inside an unstable sort buys nothing.