Why choose heapsort over a faster quicksort for firmware with a hard worst-case latency budget and no allocator?

## The argument is about which number is defensible A colleague with a benchmark chart is answering a different question from the one the deadline asks. Benchmarks measure the *average* on the inputs someone chose; a hard latency budget is discharged against the *maximum* over all inputs the system can actually receive. Those two numbers can differ by orders of magnitude, and only one of them appears in a timing analysis. Set up the comparison on the properties that matter to the constraint, not on throughput: | Property | Heapsort | Partition-based (quicksort) | Merge-based | |---|---|---|---| | Worst-case time | O(n log n) guaranteed | O(n^2) with weak pivots | O(n log n) guaranteed | | Auxiliary space | O(1) | O(log n) stack if depth-controlled | O(n) buffer | | Dynamic allocation | none | none | typically required | | Stack depth | none if iterative | bounded only with care | recursion depth | | Stable | no | typically no | yes | | Average speed | slowest of the three | fastest | middle | Read down the constraint column — bounded time, no allocator, bounded stack — and heapsort is the only entry that satisfies all three without an argument. The merge-based sort dies on the allocator rule; the partitioning sort dies on the worst case unless you add machinery. ## Answering the three counterarguments you will actually get **"Randomise the pivot and the quadratic case disappears."** It becomes improbable, not impossible. A probabilistic bound is not a bound; a certification argument cannot rest on an input distribution nobody has characterised, and adversarial or merely unlucky data is a real possibility when input comes from the field. Randomisation also introduces run-to-run non-determinism, which complicates reproducible replay of a recorded incident — often an explicit requirement in the same class of system. **"Median-of-three fixes sorted input."** It removes the classic sorted-input trigger and leaves others; heavy duplicate runs still degrade schemes that do not partition three ways, and pivot heuristics remain heuristics. Every mitigation you bolt on is more code inside the certification boundary, which is a cost, not a free win. **"Our data is never adversarial."** This is a claim about the world, and it will be wrong eventually — a firmware update changes an upstream sampling rate, a configuration table arrives pre-sorted, a sensor saturates and emits a long run of identical values. The value of a guaranteed bound is exactly that it survives being wrong about your inputs. ## Being honest about what heapsort costs you A principal-level answer does not oversell. Heapsort is unstable, so if any consumer relies on tie order you must encode that in the key rather than in the sort. It is non-adaptive, so nearly-ordered input buys nothing. And it is measurably slower on average than partitioning because of its scattered access pattern — on large data, a small multiple. If average throughput is also a requirement, say so and offer the hybrid: partition normally, count recursion depth, and switch to heapsort past a depth limit. That gives fast typical behaviour with an O(n log n) ceiling — and adds a second algorithm's worth of code paths, tests and review burden inside the trusted boundary. Whether that trade is worth it is a team decision about maintenance capacity, not a purely technical one. ## The questions to ask before the argument even starts - **How large is n, and is it bounded?** If the array is a few dozen elements with a hard cap, insertion sort is O(n^2) but with a tiny constant and a trivially provable bound at that cap — and it is a dozen lines anyone can review. Asymptotics do not decide small-n questions. - **Is sorting on the critical path at all?** Sometimes the fix is to keep the data ordered on insertion, or to sort off the deadline path entirely, which dissolves the choice. - **What is the actual budget, and what does the analysis need?** A measured worst case on representative hardware, with the sort's stack usage and its absence of allocation stated explicitly, is what closes the analysis — the algorithm choice is in service of producing that evidence. - **Who maintains this in five years?** A single well-understood iterative sort with an obvious bound is easier to keep correct than a tuned hybrid. That is a legitimate input to the decision, and stating it is part of owning it. ## How to run the disagreement Do not argue chart against chart. Agree on the acceptance criterion first — worst-case latency at the maximum input size, plus the no-allocation and stack-bound rules — then measure both candidates against *that* criterion, including a deliberately adversarial input for the partitioning sort. The decision follows from the criterion, and the colleague with the benchmark ends up agreeing with the method rather than losing an argument.