Problem. Compare QuickSort, MergeSort, and HeapSort across time, space, and stability — and say when you'd reach for each.
The comparison
| Operation | Best | Average | Worst | Note |
|---|---|---|---|---|
| QuickSort | O(n log n) | O(n log n) | O(n²) | in-place O(log n) stack, unstable |
| MergeSort | O(n log n) | O(n log n) | O(n log n) | O(n) extra space, stable |
| HeapSort | O(n log n) | O(n log n) | O(n log n) | in-place O(1), unstable |
How to read the table
QuickSort partitions around a pivot and recurses on each side. It's the fastest in practice — tight inner loop, great cache locality, in-place — which is why the JDK uses it for primitives. The catch is the O(n²) worst case when pivots are consistently bad (e.g., already-sorted input with a naive first-element pivot). Randomized or median-of-three pivots make that worst case astronomically unlikely.
MergeSort splits in half, sorts each, and merges. The merge step gives it a rock-solid O(n log n) worst case and stability, but it pays O(n) auxiliary space. It's the choice when you need stability, predictable bounds, or you're sorting linked lists (merge needs no random access) or external/streamed data.
HeapSort builds a max-heap in O(n), then repeatedly extracts the max. It's the only one that is both O(n log n) worst case and truly in-place O(1) — making it the safe pick under hard memory limits or where worst-case guarantees matter (it's used as the fallback in introsort when quicksort recursion goes too deep). Its weakness is poor cache locality (it jumps all over the array), so its constant factor is the worst of the three.