What does a stable sort guarantee when you re-sort already-ordered results by a second key?

## The definition, stated precisely A sorting algorithm is **stable** if, for every pair of records that compare **equal** on the sort key, the record that appeared earlier in the input also appears earlier in the output. It says nothing about records with different keys — those are placed by the ordering itself — and it says nothing about how fast the sort is or how much memory it uses. It is a single, narrow guarantee about ties. The direction of the claim matters. Stability does **not** say the output is unique, does not say the algorithm is deterministic, and does not say equal records are "kept together" in any richer sense than their original relative order. ## Why anyone cares: chained sorting Imagine a flight-results page. The user first orders by departure time, then clicks the price column. Two implementations are possible: 1. **One comparison pass over a key tuple.** Compare price; if equal, compare departure time. Correct, explicit, and independent of the sort's tie behaviour — but you must know all the keys up front. 2. **Chained stable sorts.** Sort by departure time, then sort by price with a **stable** algorithm. The second pass moves records into price order and leaves the earlier arrangement intact among equal prices, so the result is price-major, time-minor. The second approach is what makes interactive, user-driven ordering cheap: each click is one sort by one key, and the accumulated key priority is simply the reverse of the click order. It only works if the sort is stable. Swap in an unstable algorithm and the page still looks sorted — the price column is monotone — but the ordering inside each price bucket is scrambled. This is the classic silent regression: nothing throws, the visible column is right, and the only symptom is a test that asserts a full expected row order failing intermittently as data changes. ## Stability is not determinism The most common wrong answer is "stable means you get the same output every time." A sorting algorithm with no randomness gives the same output for the same input whether or not it is stable; an unstable sort can be perfectly reproducible and still put equal records in an order that has nothing to do with their arrival. The two properties are independent: - *Deterministic* relates one run to another run on the same input. - *Stable* relates the output to the input on a single run. A related trap: an unstable sort's tie order can shift when unrelated parts of the input change, when the input size crosses an implementation threshold, or when the algorithm behind an interface changes. Determinism today is not stability tomorrow. ## When stability buys nothing If equal keys are **indistinguishable** — sorting bare numbers with no payload attached — stability is unobservable, because swapping two equal values produces a result nobody can tell apart. Stability becomes meaningful exactly when a record carries more than its sort key: an identifier, a timestamp, a row of display data. That is also why the guarantee is discussed most in the context of records and objects, and why a fully specified comparison that breaks every tie makes stability moot. ## The cost side Stability is not free, and mainstream runtimes have made visibly different calls about it, which is why the property is worth asking about rather than assuming. Among the classic comparison sorts, insertion sort is stable and needs no buffer but is quadratic in the worst case; merge sort is stable and `O(n log n)` in the worst case but the standard array form needs `O(n)` extra space; the in-place partitioning sorts give up stability in exchange for sorting within the array. So the practical framing is: *do ties need to hold?* If yes, you are choosing between extra memory, extra comparison work (carry the original position as a final tie-break key), or an intricate in-place stable merge. If no, you have a wider menu. ## How to talk about it in an interview Say the definition in one sentence, then immediately give the chained-sort scenario, then name the cost. That order — guarantee, consequence, price — shows you treat stability as an engineering requirement rather than trivia. Finish by noting when it is irrelevant (indistinguishable equal elements, or a comparison that already breaks all ties), which demonstrates you know the boundary of the property and not just its name.