Implement merge sort and quick sort from scratch, and be ready to explain their time/space trade-offs and when each is preferable.
Fluency with the two archetypal divide-and-conquer sorts: stability, worst-case behaviour, in-place vs extra memory, and why library sorts pick one.
Both are divide-and-conquer but split the work at opposite ends. Merge sort divides POSITIONALLY into halves, recursively sorts, then does the work in the MERGE — walk two sorted halves with two pointers into one sorted output. It is always O(n log n), stable, and easy to reason about, but needs O(n) auxiliary space (and is the basis of external and linked-list sorts). Quick sort divides by VALUE — pick a pivot, partition into < and > the pivot, recurse on each side — so the work is in the partition and the combine is free. It sorts in place with O(log n) stack, averages O(n log n), and is cache-friendly (why many array sorts use it), but a bad pivot gives O(n^2), fixed in practice by random or median-of-three pivots. Family recognition signal: 'sort, or a problem that becomes easy once split and recombined' — counting inversions → merge sort; kth element → quickselect (quick sort's partition without full recursion). Rule of thumb: need stability or a guaranteed bound → merge; need in-place and average speed → quick.
Any divide-and-conquer over an array — sort, count inversions (merge), or select the kth element (quickselect). Choose merge for stability/guaranteed bound, quick for in-place average speed.
Merge: O(n log n) time, O(n) space · Quick: O(n log n) avg / O(n²) worst, O(log n) space