Sign in to watch this lesson
Algorithms - Sorting and Searching · 5:34
Elementary Sorts and the Lower Bound
We sort [5, 2, 4, 6, 1, 3] with insertion sort and watch the swap counter stop at 9, exactly the number of out-of-order pairs, which makes insertion sort O(n + inversions) and explains why it is fast on nearly sorted data (raced on this Mac) and why libc++'s std::sort uses it for tiny ranges. Selection and bubble sort are defined by their own invariants, and stability is shown on records with equal keys. Then a decision tree proves that any comparison sort needs about log2(n!) = Theta(n log n) comparisons.
You will learn
- State the loop invariant of insertion sort (sorted prefix) and selection sort (final prefix) and use it to argue correctness
- Explain why insertion sort performs exactly one swap per inversion, so it runs in O(n + inversions) and is adaptive
- Tell stability apart from sorting in place, and choose std::stable_sort when equal keys must keep their order
- Prove the Omega(n log n) lower bound for comparison sorts with a decision tree of n! leaves