Merge sort is called stable — which comparison in the merge step is what actually makes it stable?
answer
- ties are the only place order can change
- which run holds the earlier original positions?
- look at the comparison operator, not the loop
- strict versus non-strict on equal keys
- on a tie, take from the left run
basics
~20 sStability rests on one tie-break inside the merge: when the two run heads have equal keys, take the element from the left run. A strict less-than test takes the right one instead, silently reversing equal keys.
solid answer
~50 sMerge sort is not stable by nature — it is stable because of one line. In the merge loop the two run heads are compared, and the left run always holds elements that came earlier in the original array. If the test is `key(left) <= key(right)`, or equivalently "take from the right only when it is strictly smaller", equal keys leave in their original relative order and the property holds inductively at every level. Write it as strict `key(left) < key(right)` and ties are resolved in favour of the right run, so records with equal keys come out reversed. The damage is invisible on distinct keys and invisible in tests that only assert sortedness — it shows up when the sort is one stage of a multi-key ordering, where the earlier stage's ordering inside a tie group is exactly what the later stage is supposed to preserve.
code
pseudocode · 12 lines// merge sorted runs a[lo..mid-1] and a[mid..hi-1] into buf[lo..hi-1]
i = lo
j = mid
for k in lo..hi-1:
if i == mid:
buf[k] = a[j]; j = j + 1
else if j == hi:
buf[k] = a[i]; i = i + 1
else if key(a[i]) < key(a[j]): // the deciding comparison
buf[k] = a[i]; i = i + 1
else:
buf[k] = a[j]; j = j + 1go deeper
Know what stability promises: elements with equal keys leave in the order they arrived, and nothing more. Be able to give one example where that matters and one where it is unobservable.
Point at the exact line. Explain that the left run holds the earlier elements and that the tie must be resolved in its favour, then sketch why that makes the whole recursion stable by induction.
Show how you would catch this in review and in tests: duplicate keys with distinguishable payloads, asserted per tie group. Explain why sortedness assertions and unique-key test data both miss it entirely.
Decide whether the system should depend on sort stability at all. The alternative — appending a tie-breaking sequence field to the key — makes the ordering explicit and independent of which sort a future maintainer swaps in.
## What stability actually promises A sort is **stable** when elements whose keys compare equal appear in the output in the same relative order they had in the input. It promises nothing about unequal elements — those are ordered by the key — and it promises nothing at all when equal elements are truly indistinguishable, because then no observer can tell the difference. Stability is only observable when records carry payload beyond the sort key. Concretely: a reviewer is looking at a batch of document revisions, each a record of `(docId, editedAt, body)`, arriving in capture order. The batch is sorted by `editedAt`. Two revisions of different documents were saved in the same second, so their keys tie. A stable sort keeps the one that was captured first ahead of the other; an unstable one may or may not, depending on which run happened to hold it. ## Where merge sort's stability comes from It comes from a single decision in the merge, plus one structural fact. The structural fact: merge sort splits the array at a midpoint, so **every element of the left run originally sat before every element of the right run**. The left run is, by construction, the earlier half. The decision: when the two run heads compare equal, which one is emitted first? If the left one is emitted, original order among equals is preserved at this merge. If the right one is emitted, the two are swapped relative to their input positions and stability is gone. Here is the merge with the deciding line marked: ``` if key(a[i]) < key(a[j]): // strict: on a tie this falls through to the right run take a[i] else: take a[j] ``` With a strict `<`, a tie sends control to the `else` branch and the **right** element is emitted first. That is the bug. The fix is one character — `<=` — or, equivalently, invert the test so that the right run is chosen only on a strict win: `if key(a[j]) < key(a[i]): take a[j] else: take a[i]`. ## Why one line is enough — the induction Stability of the whole algorithm follows by induction on the recursion. A run of one element is trivially stable. Suppose both child runs are sorted and internally stable. In the merge, two equal-key elements are either both in the left run (their order is preserved because the merge drains a run in order), both in the right run (same argument), or one in each — and in that last case the left one came earlier in the input, and the `<=` tie-break emits it first. So the merged run is stable, and the property propagates all the way to the root. Break the tie-break and the induction fails at the very first merge that sees a cross-run tie. ## Why the bug survives review and testing Three reasons, all worth saying out loud: 1. **Correctness is unaffected.** The output is still fully sorted by key. Any assertion of the form "output is non-decreasing" passes. 2. **Distinct keys hide it.** Randomly generated test data with unique keys never produces a cross-run tie, so a property test can run a million cases and never fail. 3. **The blast radius is downstream.** Stability usually matters because the sort is one stage of a chain — order by one field, then by another, relying on the earlier ordering surviving inside tie groups. The observed symptom is a wrong final ordering two stages away from the defective line. The test that catches it: build an input with **duplicate keys and distinguishable payloads**, sort, and assert that within each equal-key group the payloads appear in their input order. ## Degrees of freedom across ecosystems Stability is a choice, not a law, and mainstream runtimes have made different calls: the Java and Python standard libraries guarantee a stable ordering for their general object sorts, while the classic C and C++ standard sort functions do not — the C++ library exposes stability as a separate, explicitly named function precisely because the stable version costs extra memory. That split is the concept's real degree of freedom: stability is worth buying when records carry payload and worth skipping when they do not. ## Related traps - **The bottom-up variant needs the same rule.** Pairing blocks left-to-right within a pass keeps the "left run is earlier" invariant; the same `<=` tie-break then keeps it stable. - **Sorting on a composite key is not the same as stability.** You can always break ties explicitly by adding a sequence number to the key. That is a legitimate alternative, and it makes stability irrelevant — but it changes the comparator, not the algorithm. - **Stability is not determinism.** An unstable sort can be perfectly deterministic and still reorder equal keys.
- All the keys in this dataset are unique — does the tie-break still matter?Not for today's data: with no equal keys there is no cross-run tie, so the two versions produce identical output. It matters because uniqueness is a property of the current input, not of the code. The day a key collides — a coarser timestamp, a second source merged in — the ordering changes silently and nothing fails loudly.
- How would you write a test that actually catches a broken tie-break?Feed records with deliberately duplicated keys and distinct, ordered payloads, then assert that within every equal-key group the payloads come out in their input order. Asserting only that the output is non-decreasing passes with the bug in place, and random data with unique keys never triggers it.
- Does the bottom-up, iterative form of merge sort keep stability?Yes, under two conditions: each merge takes from the left run on ties, and each pass pairs blocks left-to-right so the left block always holds the earlier elements. Both hold in the standard formulation, so bottom-up merge sort is stable exactly as the recursive form is.
Two piles of dated slips are being interleaved into one. When the top slip of each pile carries the same date, always take the one from the pile that was filed earlier — that single habit is what keeps same-date slips in their original order.
saying these in an interview costs you the question
- Says merge sort is inherently stable, whatever the merge does
- Thinks stability means the same input always gives the same output
- Believes stability matters only when whole records are equal
- Takes from the right run on ties to keep the merge balanced
- Claims a stable sort preserves the input order of all elements