🌳 Heapsort

Build a champion-on-top pile. Heapsort treats the array as a family tree: the element at index $i$ is the parent of the elements at $2i+1$ and $2i+2$. A max-heap just means every parent beats both its children, so the overall champion ends up at the very top, index $0$. The first phase, BUILD-MAX-HEAP, shuffles people into that shape from the bottom up.

Pull the top, repair, repeat. Once the champion sits at index $0$, swap it to the back of the array (its final sorted home) and shrink the heap by one. The new index-$0$ element is probably too small, so it "sifts down," trading places with its larger child until parents beat children again. Do this $n-1$ times and the array comes out sorted. The dashed heap boundary line in the sim marks where the finished, sorted tail begins.

Count the work. With $n=16$, building the heap takes only about $n$ cheap fixes, and each of the $\sim16$ extractions sifts down through at most $\log_2 16 = 4$ levels — roughly $16\times4 = 64$ settle-steps. Compare that to a scan-and-pick sort's $16^2 = 256$ comparisons. The gap widens fast as $n$ grows: heapsort runs in $O(n\log n)$.

The precise picture. BUILD-MAX-HEAP is actually $O(n)$, not $O(n\log n)$, because most nodes sit near the leaves where sifting is short — the cost sum $\sum_{h\ge 0} h/2^h$ converges to $2$. The extraction phase, $\sum_{i=1}^{n-1}\log i = O(n\log n)$, dominates. That bound holds in the best, average, and worst case, all using only $O(1)$ extra space — heapsort's signature guarantee. The Array Size slider sets $n$; the Preset menu feeds it sorted, reversed, or nearly-sorted inputs.

Try this in the sim above. (1) Set a large $n$ and watch the BUILD phase finish with only a handful of swaps before the heap boundary appears — that is the $O(n)$ build. (2) Open Tree View and step through one SIFT-DOWN: the highlighted node falls at most $\lfloor\log_2 n\rfloor$ levels. (3) Switch the Preset between "Reverse Sorted" and "Random" — the comparison and swap counts barely budge, showing why heapsort's worst case is no worse than its best.

Step 1 — SIFT-DOWN cost. One SIFT-DOWN from height h in a heap of size n costs at most 2h comparisons (compare with left child, compare with right child at each level). Height of root = ⌊log₂n⌋.

Step 2 — BUILD-MAX-HEAP analysis. There are at most ⌈n/2^(h+1)⌉ nodes at height h. Total cost: \[T_{build} \le \sum_{h=0}^{\lfloor\log n\rfloor} \left\lceil\frac{n}{2^{h+1}}\right\rceil \cdot 2h = n\sum_{h=0}^{\infty}\frac{h}{2^h} = n \cdot 2 = O(n)\] Therefore BUILD-MAX-HEAP is O(n), NOT O(n log n)!

Step 3 — HEAPSORT extraction phase. Extract-max n−1 times. Each extraction: O(1) swap + SIFT-DOWN on heap of size i (i from n−1 down to 1). SIFT-DOWN costs O(log i) ≤ O(log n). Total: Σᵢ₌₁ⁿ⁻¹ O(log i) = O(log(n!)) = O(n log n) by Stirling's approximation.

Step 4 — Overall complexity. T(n) = T_build + T_extract = O(n) + O(n log n) = O(n log n). This holds for ALL cases (best, average, worst). Heapsort is the only comparison sort with guaranteed O(n log n) AND O(1) space.

Step 5 — Space complexity. In-place algorithm: O(1) extra space. The heap is maintained within the input array itself using the implicit binary tree representation: parent(i)=⌊(i−1)/2⌋, left(i)=2i+1, right(i)=2i+2.

Step 6 — Stability. NOT stable. During SIFT-DOWN, non-adjacent equal elements can be reordered. Cannot be made stable without O(n) extra space.

Step 7 — Practical performance. Despite optimal asymptotic bounds, Heapsort is ~2–5× slower than Quicksort in practice due to poor cache behavior: SIFT-DOWN accesses A[2i+1] and A[2i+2] which are far apart in memory for large arrays. Memory access pattern is nearly random at large scales.