A lesson from the data structures and algorithms bootcamp. About a 12 minute read.
You will almost never write a sort. You will constantly DECIDE to sort, and that decision is a real one: you are spending O(n log n) to buy a property that makes everything afterwards easy. Knowing how the standard sorts work matters less than knowing what sorting buys, what it costs, and the one property (stability) that quietly decides whether multi-key sorting behaves.
Every comparison-based sort has a lower bound of n log n comparisons, and the argument is short enough to carry in your head. There are n! possible orderings of n items, each comparison has two outcomes so it can at best halve the set of orderings still possible, and you must narrow n! down to 1, which takes at least log2(n!) comparisons. By Stirling's approximation that is about n log2(n) - 1.44n. So merge sort is not merely a good algorithm, it is asymptotically optimal for anything that works by comparing pairs, and no cleverness will beat it while that is all you do. This is one of the few genuine impossibility results in an introductory curriculum and it is worth being able to sketch.
The rest of this lesson continues with 5 further sections. See the full curriculum.
Browse all 536 practice puzzles