Sorting user-supplied data under a hard p99 budget — do you pay for a worst-case guarantee?

## Averages and tails are different products A throughput-oriented batch job cares about total work: if one sort in ten thousand takes twenty times longer, the batch still finishes and nobody notices. A request-path service with a hard p99 target cares about the *shape of the distribution*: the target is literally defined by the slowest one percent of requests. Two algorithms with identical averages and different tails are not interchangeable there. This is where the direction of complexity claims matters. Big-O is an **upper bound**, so labelling an algorithm O(n^2) does not assert it ever exhibits quadratic behaviour on your data. Conversely, an average-case bound promises nothing about any individual run. "Quicksort is O(n log n) on average" and "this request will finish in the budget" are different statements, and the gap between them is exactly what a p99 target charges you for. ## User-supplied input removes the probability argument The usual defence of an algorithm with a bad worst case is that the bad case is astronomically unlikely on real data. That defence assumes the data is *not chosen by someone who read your code*. When the input comes from users: - A **deterministic pivot rule** — first element, last element, median-of-three at fixed positions — is reproducible. Given the rule, one can construct an input that forces maximally unbalanced partitions at every level, driving the sort to quadratic time and, in a recursive implementation, to O(n) stack depth. A crash from stack exhaustion often arrives before the slow response does. - A **duplicate-heavy** payload is the accidental version of the same attack, and it needs no malice at all: it just needs a field with few distinct values and a partitioning scheme that does not group equal keys. The correct mental model is the same one used for hash collisions: an input distribution assumption is not a security property. ## The ladder of fixes, in order of strength 1. **Randomised pivot selection.** Expected O(n log n) on every input, because the algorithm's behaviour no longer depends on the input's arrangement alone. This defeats the adversary — no input can be chosen in advance to be bad — but it does **not** provide a worst-case guarantee. The quadratic outcome remains possible with vanishing probability. Claiming otherwise is one of the most common wrong answers in this area. 2. **Depth-limited hybrid.** Run the partition-based sort, but count recursion depth; past roughly 2·log2(n) levels, switch the remaining range to an algorithm with an O(n log n) worst case. This keeps the good average behaviour and caps the bad case outright. It is why mainstream unstable library sorts are safe to use on hostile input, and it is usually the right answer: you get the guarantee without owning a new algorithm. 3. **A guaranteed algorithm outright.** A stable merge hybrid (O(n log n) worst case, O(n) space) or heapsort (O(n log n) worst case, in-place, poor locality) when the guarantee is more valuable than the constant factor. 4. **Bound the problem instead of the algorithm.** Cap how many elements a single request may sort and reject or paginate beyond that; pre-group the data so each sort is small; precompute the ordering off the request path so the tail lives in a batch job where it is harmless. This is frequently the highest-leverage move, and it is the one candidates skip. ## The organisational half of the decision The technical comparison rarely settles it alone. A bespoke sort is not a one-time cost: - It is code that must be reviewed, and sorting code has famously subtle boundary and tie-handling bugs — including bugs that lived undetected in widely used library implementations for years. - It needs its own test discipline: property tests against a reference ordering, adversarial and duplicate-heavy inputs, and a fuzzer. - The knowledge concentrates in whoever wrote it, and it is the code nobody wants to touch after they leave. So the honest principal answer usually reads: take the guarded standard sort, verify the guarantee it actually provides on your platform (stability and worst-case behaviour genuinely differ between mainstream libraries — some default sorts are stable adaptive merges, others are unstable depth-limited partition hybrids), and pay for a custom sort only when a *measured* profile shows sorting is the dominant cost and a specific key structure offers a large win, such as fixed-width byte keys that a radix pass handles linearly. ## Deciding it in the room Good answers to "which do you take?" carry four elements: the budget the decision is measured against, who supplies the input, the specific guard that caps the tail, and the ongoing cost of owning whatever you chose. Answers that name only the faster algorithm are answering a different, easier question.