14. Sorting

Sorting puts order into data so that later steps become easy. Merge sort splits in half, sorts both halves and merges them, always O(n log n). Quick sort partitions around a pivot. Counting and bucket sort beat n log n when values come from a small range.

In Java, Arrays.sort(int[]) sorts primitives, while Arrays.sort(T[], comparator) and list.sort(...) take a custom order. Many hard problems are "merge sort plus counting while you merge".