quicksort
Quicksort is the other great divide-and-conquer sort, but it does its work before recursing rather than after. Pick one element as the pivot, then partition the rest into two groups: everything smaller than the pivot goes left, everything larger goes right. Now the pivot sits in its final, correct position, and you recursively quicksort the left and right groups. When the partitions shrink to nothing, the array is sorted — no merge step needed.
The heart of it is partitioning, and it's done by swapping elements within the same array, so quicksort sorts in place using only O(log n) stack space for the recursion. Picture lining people up by height around a chosen 'reference' person: shuffle everyone shorter to the left and taller to the right; that reference person never needs to move again.
When pivots split the array roughly in half each time, the recursion is ~log n deep with n work per level — O(n log n) average time, and in practice quicksort's small constants and cache-friendly in-place swaps make it the fastest general sort. The danger is a bad pivot: if you repeatedly pick the smallest or largest element (e.g. on already-sorted data with a naive 'first element' pivot), partitions become wildly unbalanced and you slide to O(n^2). Good implementations dodge this with randomized or median-of-three pivots. Note quicksort is not stable.
void quicksort(std::vector<int>& a, int lo, int hi) {
if (lo >= hi) return;
int pivot = a[hi], i = lo;
for (int j = lo; j < hi; ++j)
if (a[j] < pivot) std::swap(a[i++], a[j]); // partition
std::swap(a[i], a[hi]); // pivot to its place
quicksort(a, lo, i - 1);
quicksort(a, i + 1, hi);
}After partition, pivot is in its final slot; recurse on the two sides. Average O(n log n), worst O(n^2).
Quicksort is average O(n log n) but worst-case O(n^2); merge sort is O(n log n) always. Quicksort wins in practice on speed and memory (in-place), merge sort wins on worst-case guarantees and stability. C++'s std::sort uses introsort — quicksort that switches to heapsort if recursion goes too deep, capping the worst case at O(n log n).