Algorithms from zero
Sorting and search: free-recall review
Retrieval beats re-reading. For each prompt, say or write a full answer from memory before you open the model answer — the effort of recall is what makes the unit stick.
Reconstruct the unit’s core ideas — sorting as preprocessing, why merge sort and quicksort behave so differently, the binary-search invariant, and binary search on the answer — without looking back at the lessons.
- 01Why is sorting called preprocessing, and what is the rule for deciding whether to sort?
- 02All simple sorts are O(n²), yet insertion sort is still useful. Why, and how does it differ from selection sort on nearly-sorted input?
- 03Why is merge sort O(n log n) on every input, and what does it cost you for that guarantee?
- 04Quicksort is O(n log n) on average but O(n²) in the worst case. Explain the gap and how production code defends against it.
- 05State the binary-search invariant and the three classic bugs that violate it.
- 06What is 'binary search on the answer', and what precondition must hold for it to be correct?
If you could reconstruct each answer from memory, you hold the unit’s spine: sort only to reuse order; insertion sort adapts while selection sort never does; merge sort guarantees O(n log n) and stability at the price of O(n) memory; quicksort trades the worst case for in-place speed and defends it with smart pivots; and binary search — whether over an array or a monotonic answer space — lives or dies by its inclusive invariant.