Mergesort
Split the list in half, sort each half, merge them back — O(n log n) in every case, no exceptions.
Described by John von Neumann in 1945, which makes it one of the oldest algorithms still running in production. The merge step walks two already-sorted lists and takes the smaller of the two front elements each time, which is linear; the recursion is log n deep; the product is the guaranteed complexity.
Two properties make it hard to replace. It is stable — equal elements keep their relative order, which is required when sorting by several fields in sequence. And it only ever reads sequentially, making it the standard choice for data too large for memory: external sorts on disk and tape still rest on mergesort. The cost is O(n) extra memory, where Quicksort needs almost none but degrades to quadratic time in the worst case. Python's and Java's default sorts use Timsort, a hybrid that is mergesort underneath.