Why Sorting Matters

Sorting is a preprocessing step that makes hard problems easy.

What sorting enables:

$1.$ Binary search: Find elements in $O(\log n)$ instead of $O(n)$.

$2.$ Two pointers: Find pairs with a target sum in $O(n)$ instead of $O(n^2)$.

$3.$ Greedy algorithms: Many greedy solutions start by sorting (activity selection, interval scheduling).

$4.$ Duplicate detection: Adjacent elements after sorting reveal duplicates in $O(n)$.

$5.$ Efficient merging: Merge $k$ sorted lists in $O(\sum \text{length of arrays})$ or $O(n)$.

If you skip sorting, you'll write $O(n^2)$ solutions where $O(n \log n)$ exists.