A teammate wants to replace merge sort with in-place quicksort to save memory — how do you respond?

## Answer the requirement question before the algorithm question The proposal frames the choice as memory versus memory. It is not. Merge sort and in-place quicksort differ on three properties at once — stability, worst-case time and auxiliary space — and only one of them is on the table in the proposal. The senior move is to name all three before agreeing to anything. **Stability.** Ask: does anything downstream depend on the order of records whose sort keys are equal? The usual reason it does is chained sorting: results ordered by one key, then re-sorted by a second, with the earlier ordering surviving inside ties. Under an unstable sort the visible column is still monotone, so it looks right; only the ordering inside each group of equal keys changes. There is no exception, no failure, and no obvious symptom — often just a test that asserts a full expected ordering and starts failing as the data drifts. Treat that as a behaviour change requiring the same scrutiny as any other contract change, not as an implementation detail. **Worst case.** Merge sort is `O(n log n)` on every input. Quicksort with a naive first-or-last pivot is `O(n^2)` on organised input — sorted, reverse-sorted, or heavily duplicated data with a poor partitioning scheme — which is exactly the shape production data likes to take. Mitigations are well known: randomised pivots, median-of-three, three-way partitioning for duplicate-heavy keys, and a depth-triggered fallback to heapsort to cap the worst case. If the proposal does not include one of these, the change trades a guarantee for an average. **Space, measured rather than assumed.** "In place" means small auxiliary space, not none. Recursion depth is space: an implementation that recurses into the smaller partition and iterates on the larger holds `O(log n)` frames; one that always recurses left can reach `O(n)` depth on adversarial input, and stack exhaustion is a crash rather than a slowdown. On the other side, ask what the merge buffer actually holds. If you are sorting references to records — the common case for anything with a payload — the buffer is `n` references, while the records themselves are untouched. Against a working set that already holds those records, a buffer of references is frequently a small percentage, not a doubling. The proposal deserves a number, not an intuition. ## What you can actually do if the ceiling is real Suppose the memory ceiling is genuine — a fleet-wide limit, a batch job that must fit alongside other work — and tie order is genuinely required. There are several honest options, each with a stated price: 1. **Sort a smaller thing.** Sort an array of references, or of `(key, original position)` pairs, then permute the records once. This shrinks both the buffer and the data movement, and it is usually the largest win available. 2. **Force stability onto an unstable sort.** Add the original position as the final tie-break in the comparison, so no two records ever compare equal. This makes any algorithm behave stably. The price is an extra field per record — which itself costs `O(n)` and may cancel the saving — plus one extra comparison on every tie. It is a real technique, not a free lunch. 3. **Use an in-place stable merge.** Block-rotation merging reaches constant extra space while preserving tie order, but does substantially more data movement and is significantly harder to implement and maintain. Only justified when the ceiling is hard and the alternatives have been measured. 4. **Accept instability, explicitly.** If nothing depends on tie order, say so in writing and add a test that documents the new contract, so the next engineer does not accidentally reintroduce a dependency on it. ## The organisational half of the answer The reason this question is asked at senior level is that the failure mode is social, not technical. An algorithm swap that changes tie ordering passes review because reviewers check whether the output is sorted, and it is. The defence is to make the requirement explicit: if tie order matters, there should be a test asserting the full expected order of a tied group, named so it reads as a contract rather than as an incidental assertion. Then any future swap — a refactor, a dependency upgrade, someone else's optimisation — fails loudly instead of shipping a subtly different page. ## How to say it in an interview Don't answer "no" and don't answer "yes". Answer with three questions in order: *does anything depend on tie order; what does the buffer actually hold; and what is the worst-case bound we are giving up?* Then give the fallback that satisfies both constraints — sort references, or decorate with position — and finish with the test that pins the behaviour. That sequence shows you evaluate a change by its contract impact first and its resource impact second, which is exactly the judgment the question is probing.