When would you approve hand-rolled insertion sort on a hot path instead of the standard sort?

## The shape of the proposal A service drains batches of event records from an ingestion queue and needs them in timestamp order before writing them downstream. Producers stamp the records; network batching and a little clock jitter leave each record within a few positions of its correct place. An engineer proposes replacing the general-purpose sort on this path with a hand-written insertion sort, arguing that the input is nearly ordered so the sort will be effectively linear and allocation-free. The argument is not wrong. Insertion sort's cost is `O(n + d)` where `d` is the total displacement (the number of inversions), it is in-place, and on a batch that is 3-sorted it will genuinely beat a general sort that pays its structural `n log n` regardless. The question is not whether the claim can be true — it is what has to be established before it becomes a production dependency, and what happens on the day it stops being true. ## What I require: evidence 1. **The displacement distribution, from production, at the tail.** "Records arrive nearly in order" is a claim about an upstream system. I want the measured distribution of inversions per batch over a period that includes a deploy, a restart and a peak — and I want p99 and max, not the mean. A path that is linear 99% of the time and quadratic 1% of the time is a path with a bad tail, and tail latency is what pages people. 2. **A benchmark at realistic batch sizes with realistic records.** Displacement is not the only variable; record size drives the cost of each move. Sorting 200 small records and sorting 5,000 fat ones are different experiments. 3. **The size of the win.** If the general sort costs 400 microseconds and the specialised one costs 380, the proposal is noise dressed as an optimisation, and I decline on maintenance grounds alone. If it removes a per-batch allocation and cuts the step from 400 microseconds to 40 on a path that runs thousands of times a second, that is a real argument. ## What I require: containment The assumption behind the optimisation is owned by a team that does not know it exists. Backfills, replays after an outage, a producer that starts batching differently, a clock correction, a new partition strategy — any of these can turn near-ordered into arbitrary, with no code change on our side. So the fallback is not optional: - **Bound the work.** Count shifts (or measure displacement in a first pass) and, when the count crosses a threshold proportional to the batch size, abandon and run the general sort. The wasted partial work is bounded by the threshold, and the worst case becomes "a bit slower than the general sort" instead of "quadratic stall". - **Make the fallback observable.** Emit a metric each time it fires. A silent fallback that starts firing on every batch means the optimisation stopped paying months ago and nobody noticed. - **Cap the blast radius.** If the batch size is unbounded, bound it — quadratic growth is what turns a 10x traffic increase into a 100x cost increase. ## What I require: ownership A hand-written sort is a permanent liability with a small, permanent payoff. It needs property-based tests against a reference sort (same multiset out, ordering correct, stability preserved if downstream depends on it), explicit adversarial cases — reversed, all-equal, single element, empty, all-but-one ordered — and a comment stating the invariant and the assumption it exploits. It also needs to be small enough that the next person can read it. Twelve lines with a stated invariant is a reasonable thing for a team to own; a cleverly unrolled variant with a tuned threshold and three special cases is not, unless the path is genuinely hot enough to fund it. ## The 10x question Every approval of an asymptotically worse algorithm should come with an answer to "what happens at 10x". Here it is arithmetic: with displacement staying proportional to batch size, cost grows linearly and everything is fine. With displacement growing with the square of the batch size — which is what happens if batches get larger by merging more producers with independent jitter — cost grows quadratically. So the honest approval is conditional: it holds while the *per-record* displacement stays bounded, and that is the property to alert on, not batch size alone. ## How I would phrase the decision Approve when: the displacement is measured and bounded at the tail, a shift-budget fallback exists and is instrumented, the win is large on a genuinely hot path, and the code is small and tested against a reference. Decline when: the near-ordered claim rests on reasoning about the producer rather than data, there is no fallback, or the measured improvement is small. And write down the conditions in the code, because the reviewer in two years will otherwise see only a hand-rolled quadratic sort on a hot path and either delete it or, worse, copy it somewhere the assumption does not hold.