Which of insertion, merge, quicksort and heapsort are stable, and which sort in place?
answer
- three axes, four algorithms
- which one buys order with memory
- which one is in place but scrambles ties
- long-range swaps break arrival order
- no classic sort gives both for free
basics
~20 sInsertion sort and merge sort are stable; quicksort and heapsort are not. Insertion sort, quicksort and heapsort work in place, with quicksort still spending recursion stack. Standard merge sort is the odd one out: stable, but it needs a linear-size buffer.
solid answer
~50 sInsertion sort is stable, in place and adaptive. Merge sort is stable and `O(n log n)` in the worst case, but the standard array form buys stability with an `O(n)` buffer. Quicksort partitions within the array, so it is in place apart from `O(log n)` recursion state, but the long-range swaps that partitioning performs cross equal keys, so it is unstable — and with a naive pivot it is `O(n^2)` in the worst case. Heapsort is in place and `O(n log n)` in the worst case but also unstable, because each extraction moves the last element to the root and equal keys leapfrog each other. The two cells candidates miss are exactly the interesting ones: heapsort is in place yet unstable, and merge sort is stable yet not in place — no classic algorithm gives you both for free.
go deeper
Recall which of the four common sorts are stable and which sort within the array, and be able to name the extra memory the standard merge sort needs.
Explain the mechanism behind each answer: long-range swaps destroy tie order, and a merge step needs somewhere to write. An interviewer wants the reason, not the table.
Demonstrate that you pick per workload — payload size, whether ties are observable, whether a worst-case bound is required — and that you know recursion depth counts as memory.
Own the standardisation call: whether teams may choose sorts freely, or whether a stability and memory contract is fixed centrally so a future swap cannot silently change behaviour across services.
## Three independent axes The classic sorts are usually compared on running time alone, but interviews test three orthogonal properties: - **Stability** — do records with equal keys keep their input order? - **In place** — does the algorithm sort within the input storage, using only a small amount of extra space (constant, or logarithmic for recursion state)? - **Adaptivity** — does it do less work when the input is already partly ordered? A property on one axis implies nothing about the others, which is why a matrix beats a ranked list. ## The matrix | Algorithm | Stable | In place | Adaptive | Worst-case time | |---|---|---|---|---| | Insertion sort | yes | yes | yes (`O(n + inversions)`) | `O(n^2)` | | Merge sort (standard array form) | yes | no (`O(n)` buffer) | no (classic form) | `O(n log n)` | | Quicksort (in-place partition) | no | yes, plus `O(log n)` stack | no | `O(n^2)` with a naive pivot | | Heapsort | no | yes | no | `O(n log n)` | Note what the table does *not* say. `O(n^2)` for quicksort is an upper bound reached on adversarial or already-organised input under a naive pivot rule; it is not a prediction about typical data, where quicksort's small constants usually make it the fastest of the four. And insertion sort's `O(n^2)` label hides that it is linear when the input is nearly ordered — which is why production sorts use it for short runs. ## The two cells people get wrong **Heapsort: in place but unstable.** A binary heap embedded in the array does its work by swapping elements across long distances. Sift-down repeatedly exchanges a node with a child many positions away, and each extraction moves the array's last element up to the root. Two equal keys can therefore cross with no record of which arrived first. The heap structure encodes a partial order on keys and nothing else — it has no memory of arrival order to preserve. So heapsort gives you the worst-case `O(n log n)` bound and the in-place property together, and pays for that combination with stability. **Merge sort: stable but not in place.** The merge step compares the fronts of two sorted halves and, on a tie, must take from the left half to preserve order. That rule is what makes it stable — and it also needs somewhere to write the merged output, because you cannot overwrite the two halves you are still reading. Hence the `O(n)` buffer. In-place merging algorithms do exist and can preserve stability using block rotations, but they carry noticeably larger constants and considerably more implementation complexity, so the buffered form remains the default. ## Why in place does not mean zero memory Quicksort is described as in place because partitioning rearranges elements within the array itself. But recursion depth is space: each pending call frame is memory. If the implementation recurses into the smaller partition first and loops on the larger one, depth is bounded by `O(log n)`; a naive implementation that always recurses into the left side can reach `O(n)` depth on adversarial input, which is a stack-exhaustion failure, not merely a slow sort. "In place" is a claim about *small* auxiliary space, and for recursive sorts the honest statement is `O(log n)`, not `O(1)`. ## Turning an unstable sort stable Any sort can be made to behave stably by decorating each record with its original position and using that as the final tie-break in the comparison. Then no two records ever compare equal and the tie order is forced. The price is one extra field per record — `O(n)` memory, which often defeats the reason you chose the in-place algorithm — plus an extra comparison on every tie. That tradeoff, not a magic algorithm, is the honest answer to "can I have stable and in place?" ## How to present this Don't recite the table cell by cell. State the two axes, then say what each algorithm trades: insertion sort trades asymptotic time for simplicity and adaptivity; merge sort trades memory for stability and a worst-case guarantee; heapsort trades stability for the same guarantee in place; quicksort trades the worst-case guarantee and stability for the best constants. Framed as four different purchases of the same three goods, the matrix becomes something you can reconstruct rather than memorise.
- Why is heapsort in place yet unstable?Because it moves elements across long distances. Sift-down swaps a node with a child many positions away, and each extraction lifts the array's last element to the root. Two records with equal keys can cross during those jumps, and the heap keeps no information about which one arrived first — it encodes a partial order on keys only.
- Can merge sort be made in place, and why isn't that the default?Yes. In-place merging via block rotations can even keep stability, reaching constant extra space. But those schemes do substantially more data movement and extra comparisons, and are far harder to get right and to maintain. Most implementations judge a linear buffer cheaper than the constants and the complexity, especially when what is being sorted is references rather than whole records.
- Which of the four is adaptive, and what does that change?Insertion sort: its cost is proportional to the number of inversions, so nearly ordered input is handled in near-linear time. Classic merge sort does the same work regardless of order, though run-detecting merge variants are adaptive. Heapsort is essentially insensitive to input order, and naive-pivot quicksort gets worse on sorted input rather than better.
saying these in an interview costs you the question
- Heapsort is stable because a heap keeps order
- Merge sort is in place, it just recurses
- Quicksort becomes stable with a better pivot
- In place always means exactly O(1) extra space
- Unstable sorts are simply badly implemented