The O(n log n) sorts
Merge sort divides, sorts halves, and merges — guaranteed O(n log n), stable, but O(n) extra space. Quicksort partitions around a pivot — O(n log n) average and in-place, but O(n²) on bad pivots (mitigated by randomization). Heapsort is O(n log n) in-place but not stable.
Stability & when it matters
A stable sort preserves the relative order of equal keys — essential when sorting by multiple criteria in passes. Merge sort and insertion sort are stable; quicksort and heapsort are not (without extra work).
Beating O(n log n)
Counting sort and radix sort run in O(n + k) / O(d·n) when keys are bounded integers — no comparisons needed. They trade generality for speed under those constraints.