Introsort caps quicksort's worst case, so why would a library still ship a second, stable sort?

## Two different guarantees It is tempting to read introsort as strictly dominant: quicksort's speed, heapsort's ceiling, no allocation. But "fast with a bounded worst case" and "stable" are orthogonal promises, and introsort makes only the first. **Stability** means that elements comparing equal come out in the same relative order they went in. Introsort violates this twice over: partitioning swaps elements across long distances with no regard for their prior positions, and heapsort, the fallback, is unstable as well. There is no cheap patch — making a partitioning sort stable in place is a research-grade problem, not a tuning knob. ## When stability is meaningless, and when it is the whole point If the elements are plain values — numbers, or anything where "equal" implies "indistinguishable" — stability describes a property no observer can detect. Two equal values swapping places changes nothing anyone can read back. Paying `O(n)` scratch memory to preserve an unobservable property is pure cost. If the elements are records compared on one field, "equal" means *equal on that field only*, and the elements are otherwise distinct. Now ordering among ties is visible, and worse, it is something callers actively rely on: - **Multi-key sorting.** The standard idiom is to sort by the least significant key first, then by the more significant key, and let stability preserve the earlier ordering within ties. An unstable sort silently destroys the secondary ordering. - **User interfaces.** A user sorts a table by date, then by owner, and expects the date ordering to survive within each owner's rows. With an unstable sort the rows scramble, and the report is nondeterministic between runs. - **Reproducibility.** Two runs over the same input can produce different orderings of tied records, which breaks golden-file tests, cache keys derived from ordered output, and diff-based review of generated artefacts. Crucially, none of these fail loudly. The output is correctly *sorted*; only ties differ, only sometimes, and only on some inputs. It is the kind of bug that reaches production, resists reproduction, and is expensive to trace back to a sort call nobody suspected. ## Why not just ship the stable sort for everything Because the stable sort's cost is real and lands exactly where the unstable one is most valuable. A stable merge-based sort in its practical form needs an `O(n)` scratch buffer. For a fixed memory budget — a render loop ordering draw calls every frame, a device with no headroom, a hot path forbidden from touching the allocator — an allocation proportional to the data is not a slowdown but a failure mode, and the failure arrives under exactly the load you least want it under. That is the whole reason introsort's fallback is heapsort rather than a merge: the guarantee has to hold without asking for memory. Handing such a caller a stable sort takes away the property they chose the sort for. There is also a comparison-cost asymmetry. Sorting records means calling a caller-supplied ordering, often through an indirection, so comparison count dominates and memory-traffic tricks matter less. Sorting raw values means comparisons are nearly free and memory traffic dominates. The two element kinds genuinely reward different algorithms, which is why the split is not laziness. ## The pattern, and the call a lead has to make The resulting convention across mainstream ecosystems is two sorts: | element kind | sort | guarantee bought | cost accepted | |---|---|---|---| | value-like, equals indistinguishable | in-place unstable hybrid with depth-limited fallback | bounded worst case, no allocation | ties reordered (unobservable) | | records with a caller-supplied ordering | stable merge-based sort | ties preserved, adaptive on part-ordered data | `O(n)` scratch memory | The leadership judgment is about **defaults and discoverability**, not about which algorithm is cleverer. Two sorts mean two code paths to maintain and an API surface where a caller must know which one they are getting — and most callers never think about stability until it bites them. So the questions to answer for your own codebase are: what does the default do when the caller expresses no preference; is stability documented at the call site or buried in a reference page; and if the platform can only afford one general-purpose sort, which mistake is cheaper to live with — an unreproducible ordering bug in a reporting pipeline, or an allocation in a frame loop? Different runtimes have answered differently: some standard libraries default records to a stable sort and reserve the unstable in-place hybrid for primitive values, others expose both explicitly and let the caller choose. Both are defensible; what is not defensible is a codebase where nobody knows which one they are calling.