Micro-questions over the merge sort module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. The insight
1. Why are the elementary sorts quadratic, and how does merge sort attack that?
Answer
Because each element is compared against many others. Merge sort splits: sort two halves independently, then combine them.
2. Why is merging two sorted lists linear?
Answer
Walk both with one pointer each, always taking the smaller head. No element is ever compared twice against the same one, because progress is made on every comparison.
3. What guarantee does merge sort provide that no other common sort does?
Answer
in the worst case, not just on average. Quicksort is usually faster in practice and can degrade to ; merge sort cannot.
B. The cost
4. How much work does each level of the tree do?
Answer
— every element is touched once per level during merging.
5. How many levels, and why?
Answer
, because the size halves each time.
6. Why does the bound hold for every input?
Answer
Because the split is by position, not by value. Nothing about the data can unbalance it.
7. What does that last point separate it from?
Answer
Quicksort, whose split depends on the data and can therefore be unbalanced.
C. Stability
8. What single character makes merge sort stable?
Answer
The = in if left[i] <= right[j] — when the heads are equal, take from the left.
9. Why does taking from the left preserve order?
Answer
The left half came first in the original array, so preferring it keeps the original relative order of equal elements.
10. What happens with < instead?
Answer
The sort becomes unstable — a one-character difference with a real consequence.
D. External merge sort
11. 100 GB to sort, 8 GB of RAM. Why does merge sort apply where others do not?
Answer
Because merging reads sequentially.
12. Describe the two phases.
Answer
- Read as much as fits, sort it in memory, write it out as a sorted run. Repeat — about 13 runs for 100 GB at 8 GB each.
- Open all runs at once and do a -way merge, repeatedly taking the smallest head across all runs.
13. What structure makes each merge step efficient, and at what cost?
Answer
A min-heap over the run heads — per step.
14. Why does sequential access matter so much here?
Answer
Sequential disk reads are orders of magnitude faster than random ones — which is exactly why quicksort, which jumps around during partitioning, is not used.
15. Where does this actually run?
Answer
A database doing a large ORDER BY that cannot use an index, and sort(1) on a large file.
E. Traps
16. If you allocate a fresh temporary inside every recursive call, does the asymptotic complexity change? Does the running time?
Answer
Complexity: no. Running time: yes, substantially. It makes the constant much worse and stresses the allocator. Real implementations allocate one buffer of size up front.
17. What is the tail copy, and what happens if you forget it?
Answer
When one side is exhausted, the rest of the other must still be appended. Omitting it silently drops elements.
18. Is merge sort in-place?
Answer
No — it needs extra. In-place variants exist and are markedly slower and much more complex.
19. When should you not use it?
Answer
Below about 16 elements, where insertion sort wins on constants. Timsort switches for exactly this reason.
20. What changes on a linked list?
Answer
Merge sort is effectively in-place — you relink nodes instead of copying — which makes it the standard choice there.
21. Summarise merge sort in one sentence.
Answer
Split by position so nothing can unbalance it, merge linearly taking from the left on ties — guaranteed , stable, extra space, and the only one that works off disk.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- Merge Sort — the module
- Quicksort — Question Bank — the faster, riskier one
- Elementary Sorts — Question Bank — what it falls back to
Software engineering
Infrastructure & security
Computer science
Hardware & engineering