Section Recap

You've learned comparison sorts (selection, insertion, merge, quick, heap) and non-comparison sorts (counting, radix).

Quick reference:

• Small/nearly sorted: Insertion sort
• General purpose: Library sort
• Need stability: Merge sort/Timsort
• $O(1)$ space, $O(n \log n)$ guarantee: Heap sort
• Integers in small range: Counting sort
• Few digits: Radix sort

Lower bound: Comparison sorts can't beat $O(n \log n)$.