The idea: two in-place n log n sorts with different weak spots
Heap sort and quick sort both sort an array in place, without a second array, and both take about n log n steps on a typical input. The page copies one array into two lanes and runs both sorts in lockstep: one Step is one comparison on each side, plus the swaps it causes. Under the lanes, a scoreboard counts comparisons and cache misses. Those two numbers show the trade-off. Quick sort is usually faster. Heap sort is never slow.
Heap sort
Heap sort treats the array as a binary tree: the children of slot i are slots 2i + 1 and 2i + 2. The heap lane draws the same slots twice, as bars and as that tree.
- Build a max-heap. Sift down every parent, from slot ⌊n/2⌋ − 1 back to slot 0. A sift-down compares a node with its larger child and swaps while the child is larger. Afterwards every parent is ≥ its children, and the root holds the maximum.
- Sort down. Swap the root with the last slot of the heap. That value is now in its final place (green), and the heap is one slot shorter (its node fades). Sift the new root down. Repeat n − 1 times.
Each sift-down costs at most 2 comparisons per level and the tree has log₂ n levels. So heap sort needs at most about 2n log₂ n comparisons on any input. That bound is its selling point. It is not stable, and its memory access is poor (below).
Quick sort
Quick sort picks a pivot, then partitions the range: i scans right past values smaller than the pivot, j scans left past larger values, and when both stop, the two values are swapped. When the scans cross, the pivot is swapped into slot j, its final place. Then quick sort sorts each side. Every running call is drawn as a bar in the call-stack area, under the slots it sorts.
On random input the pivot splits the range roughly in half, the stack stays about log₂ n calls deep, and quick sort does about 1.4 n log₂ n comparisons, fewer than heap sort (Demo: random input).
Quick sort's bad inputs
With the first element as the pivot, an already sorted array is the worst case. Every pivot is the smallest value left, so each partition peels off one value. The stack grows n − 1 calls deep and quick sort does about n²/2 comparisons: 119 for 15 items, against heap sort's 77 (Demo: already sorted, first-element pivot). Reversed input is just as bad for quick sort. For heap sort, a reversed array is already a max-heap, so its build phase only compares and swaps nothing (Demo: reversed input).
The usual fix is a better pivot. The median of three (first, middle and last value) is the true middle of a sorted range, so the splits are even again: 62 comparisons and a stack 3 calls deep (Demo: already sorted, median-of-three pivot). Some inputs still defeat median of three, so quick sort's worst case stays O(n²).
Memory access: why quick sort is usually faster
A CPU reads memory in cache lines (64 bytes, for example 16 four-byte ints). Touching a slot whose line is not in the cache is a cache miss, which costs far more than a comparison. The page uses a tiny model cache: a line holds 4 slots, the cache holds 2 lines (yellow bands), and the least recently used line goes out. A red band is a line just loaded, which is a miss.
- Quick sort's i and j each step to the next slot, so each scan loads a line once and uses all 4 slots. Real CPUs also prefetch the next line of such a scan.
- Heap sort's sift-down goes from slot i to 2i + 1. Below the top levels every step lands on a different line. Each sort-down step also touches slot 0 and the last heap slot, which are far apart.
On 15 random items heap sort has 36 misses and quick sort 8. On 31 items it is 154 against 32 (Demo: 31 random items). Even in quick sort's sorted-input worst case, its misses stay below heap sort's (26 against 41). On real hardware this is why a good quick sort usually beats heap sort by a factor of 2 or more, despite the guarantee.
When to pick which
| Heap sort | Quick sort | |
|---|---|---|
| Comparisons, typical | ≈ 2 n log₂ n | ≈ 1.4 n log₂ n |
| Worst case | O(n log n), always | O(n²) (sorted input with a first-element pivot) |
| Extra memory | none, O(1) | the call stack: O(log n) if it recurses into the smaller side first |
| Memory access | jumps (slot i → 2i + 1), many cache misses | sequential scans, few cache misses |
| Stable | no | no |
| Pick it when | you need a hard time bound and no extra memory: kernels, embedded and real-time code, a fallback | you want the fastest general in-memory sort, with a good pivot |
Introsort: both in one
Library sorts don't choose. Introsort (C++ std::sort, .NET Array.Sort) runs quick sort with a median-of-three pivot and counts the recursion depth. If the depth passes 2 log₂ n, the pivots are going badly, so it heap-sorts that range instead. Small ranges go to insertion sort. The result has quick sort's speed on normal input and heap sort's O(n log n) guarantee on bad input. In the sorted-input demo, introsort would switch to heap sort at depth 6.
See also Heap Sort for the heap step by step, Quick Sort vs Merge Sort for quick sort's stack and memory, Heap for the data structure and Sorting Race for more pairs.
What the page leaves out
Real cache sizes (thousands of lines, and several levels), hardware prefetching and branch prediction, which all favour quick sort's simple scans even more. Also left out: three-way partitioning for many equal keys, recursing into the smaller side first to cap the stack, bottom-up heap construction tricks (Floyd's "bounce" sift-down, which saves comparisons), and dual-pivot quick sort as used by Java for primitive arrays.