Micro-questions over the quicksort module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. Why it exists
1. Compare quicksort with merge sort on memory.
Answer
Merge sort needs extra; quicksort needs only of stack.
2. Why is quicksort faster in practice despite a similar comparison count?
Answer
The reason is memory, not operation count. Partitioning sweeps sequentially and swaps in place — friendly to caches and prefetchers. Merge sort copies into and out of a separate buffer, doubling memory traffic. Constants win.
3. What is the price?
Answer
A genuine worst case. Merge sort’s split is by position and cannot be unbalanced; quicksort’s split is by value, so an unlucky input makes every partition lopsided — .
B. Partitioning
4. What does partitioning do?
Answer
Choose a pivot; rearrange so everything smaller is left of it and everything larger is right. The pivot is now in its final position. Recurse on both sides.
5. Describe Lomuto partitioning.
Answer
Pivot is the last element. Walk with j, keeping i as the boundary of the “smaller” region; swap into place whenever a[j] <= pivot. Finally swap the pivot to i+1.
6. Where does Lomuto degrade badly, and why?
Answer
On arrays of equal elements — every element satisfies <= pivot, so every partition is maximally lopsided and the sort goes quadratic on input that is already trivially sorted.
7. Describe Hoare partitioning and its advantages.
Answer
Two pointers move towards each other, swapping out-of-place pairs. It does about three times fewer swaps on average and handles duplicates far better, because elements equal to the pivot can end up on either side, which keeps partitions balanced.
8. Why is Lomuto taught first?
Answer
Only because Hoare’s index handling is fiddlier.
C. The worst case
9. What quantity actually decides the complexity?
Answer
The recursion depth. Balanced splits give depth and ; maximally lopsided splits give depth and .
10. With a last-element pivot, what is the worst case?
Answer
Already-sorted input — the pivot is always the maximum, so one side gets everything.
11. Why is that damning rather than a curiosity?
Answer
It is not a rare adversarial input; it is the most common input shape there is.
12. Give the five fixes and what each does.
Answer
| Fix | What it does |
|---|---|
| Median-of-three | pivot on median of first/middle/last — kills sorted input cheaply |
| Randomised pivot | no fixed input is worst-case; an adversary cannot predict it |
| Introsort | past depth , switch to heapsort — a hard ceiling |
| Three-way partition | split into < = >; makes duplicate-heavy arrays linear |
| Insertion sort below ~16 | better constants on small partitions |
13. What is std::sort?
Answer
Introsort with all five. That is why the standard library never exhibits the worst case even though the underlying algorithm has one.
14. Rank these three for a last-element pivot: random, reverse-sorted, all-identical.
Answer
Random is fine (). Reverse-sorted is — the pivot is always the minimum. All-identical is also under Lomuto and is the case people forget, because the array is already “sorted”.
D. Stability
15. Why is quicksort not stable?
Answer
Partitioning swaps elements across long distances. Two equal elements can be exchanged or jumped past one another, and their original order is lost.
16. Why do libraries not just fix it?
Answer
Making it stable requires extra space, which surrenders quicksort’s main advantage.
17. What do libraries offer instead?
Answer
A choice: sort (quicksort-family, unstable, fast) and stable_sort (merge-family, stable, memory). Python’s list.sort is Timsort and always stable — a deliberate different trade.
E. Traps
18. What is the Hoare off-by-one?
Answer
Hoare returns j and you recurse on [lo, j] and [j+1, hi] — not [lo, j-1]. Getting it wrong causes infinite recursion.
19. How do you cap the stack depth at ?
Answer
Recurse into the smaller side and loop on the larger. The recursed side at most halves each time.
20. Does randomisation make the worst case impossible?
Answer
No — it makes it improbable and input-independent. It is still reachable, just not by an adversary choosing the input.
21. Summarise quicksort in one sentence.
Answer
Partition in place around a pivot and recurse — the fastest in practice because it stays in cache, and safe only because libraries median-of-three it, randomise it, and cap its depth with heapsort.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- Quicksort — the module
- Merge Sort — Question Bank — the guaranteed alternative
- Heaps — Question Bank — introsort’s fallback
Software engineering
Infrastructure & security
Computer science
Hardware & engineering