Why Study Sorting?
When an input is sorted, many problems become easy (e.g. searching, min, max, k-th smallest)
Sorting has a variety of interesting algorithmic solutions that embody many ideas
- Comparison vs non-comparison based
- Iterative
- Recursive
- Divide-and-conquer
- Best/worst/average-case bounds
- Randomized algorithms