Merge sort
Also known as: Mergesort
Merge sort is a divide-and-conquer comparison sort: split the array in half, sort each half recursively, then merge two sorted runs into one.
Time is $\Theta(n \log n)$ in all cases. Classic implementations need $\Theta(n)$ auxiliary space for the merge buffer. The merge of equal keys can keep left-before-right order, so merge sort is naturally stable.
It is the conceptual core of timsort and of external sorting (merge runs from disk). Versus quicksort: worse constants and extra memory in the array case, but predictable time and stability.