A lesson from the Algorithms & Patterns module of the bootcamp. About a 12 minute read.
You will almost never write a sort. You will constantly DECIDE to sort, and that is a real decision: you are spending O(n log n) to buy a property that makes everything afterward 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 sorting by several keys works.
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 at best it halves the set of orderings still possible. You have to narrow n! down to 1, which takes at least log2(n!) comparisons, and by Stirling's approximation that is about n log2(n) - 1.44n. So merge sort is not just a good algorithm. It is as good as it gets for anything that works by comparing pairs, and no amount of cleverness will beat it while comparing is all you do. This is one of the few real impossibility results in an intro 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 576 practice puzzles