Sorting Algorithms
Understand how the classic comparison and non-comparison sorts work, and when each one is the right tool.
- • Implementing merge, quick, counting, or radix sort
- • Quickselect for the k-th element
- • Reasoning about stability and complexity
- • Choosing a sort for the input shape
- • A library sort already suffices
- • The problem is really about what you do after sorting
- • Quicksort worst case on sorted input or bad pivots
- • Losing stability when you reorder equal keys
- • Off-by-one in merge boundaries
Key Invariant
Comparison sorts bottom out at O(n log n); counting and radix beat it only when the key range is bounded