merge sort
Merge sort is a classic divide-and-conquer algorithm: split the list in half, sort each half (by the same method, recursively, all the way down to single elements which are trivially sorted), then merge the two sorted halves back into one sorted whole. The cleverness is entirely in the merge — combining two already-sorted lists is easy, because you just keep taking the smaller of the two front elements.
Picture merging two sorted stacks of cards face-up: look at the top card of each stack, take the smaller, and repeat; the output stack comes out perfectly ordered. Because the splitting halves the problem each time, the recursion is about log(n) levels deep, and merging across all the pieces at each level touches every element once — n work per level.
Multiply those together and you get O(n log n) time — and crucially this holds in the best, average, and worst case alike; merge sort has no bad inputs. The price is memory: the merge step needs a scratch buffer, so it uses O(n) extra space rather than sorting fully in place. It is stable (equal keys keep their order when ties are broken in favour of the left half), which makes it a favourite when stability matters and when sorting data too big to fit in memory (external merge sort).
void merge(std::vector<int>& a, int lo, int mid, int hi) {
std::vector<int> tmp;
int i = lo, j = mid + 1;
while (i <= mid && j <= hi)
tmp.push_back(a[i] <= a[j] ? a[i++] : a[j++]); // <= keeps it stable
while (i <= mid) tmp.push_back(a[i++]);
while (j <= hi) tmp.push_back(a[j++]);
for (int k = 0; k < (int)tmp.size(); ++k) a[lo + k] = tmp[k];
}Merging two sorted halves of total length n is O(n); doing it across log n levels gives O(n log n).
Merge sort's O(n log n) holds on every input — there is no worst-case blow-up like quicksort's. The cost you pay for that guarantee is the O(n) auxiliary array. Its recurrence T(n) = 2T(n/2) + O(n) solves to O(n log n) by the master theorem.