Heap sort — O(n log n), in-place, not stable: Visual walkthrough

We will sort this array the whole way through:

$A = [4, 10, 3, 5, 1, 8, 2]$

Seven numbers. Positions numbered $0, 1, 2, 3, 4, 5, 6$ from left. That position number is called the index — think of it as the seat number of each value.

Step 1 — Draw the array as a tree

WHAT. We are only re-drawing the same seven numbers — nothing moves yet. We just stack them in a triangle.

WHY. A flat array has no obvious "parent" or "child". But a tree does, and — this is the magic — because there are no gaps, the seat numbers obey a clean formula. For the value at seat $i$ :

$left child seat 2 i + 1, right child seat 2 i + 2, parent seat ⌊ \frac{i - 1}{2} ⌋$

$2 i + 1$ : "go down one level, take the left branch." At $i = 0$ that is seat $1$ .
$2 i + 2$ : same but the right branch — seat $2$ .
$⌊ \frac{i - 1}{2} ⌋$ : the reverse trip, back up to the parent. The $⌊ ⌋$ (floor) just chops off any fraction, because a seat number must be a whole number.

PICTURE. Follow the coloured arrows: seat $0$ (value $4$ ) points down to seats $1$ and $2$ .

Figure — Heap sort — O(n log n), in-place, not stable

Step 2 — State the goal: the heap property

WHAT. We check our tree against this rule and find it broken everywhere — seat $0$ holds $4$ but its child $10$ is bigger.

WHY this exact rule. We want the maximum to be trivially findable (just read seat $0$ ). The heap property is the weakest rule that guarantees that, while still being cheap to repair. We do not demand a fully sorted tree — that would be expensive. Just "parent beats children," locally.

PICTURE. Red edges mark every parent smaller than a child — every place the rule is violated right now.

Step 3 — The one repair tool: `sift-down`

WHAT. We fix a single out-of-place value by letting it sink to its rightful level.

WHY the larger child, not just any child? If we swapped the parent with the smaller child, the smaller child would rise above the larger one — instantly breaking the rule between the two children. Swapping with the larger child promotes the true local champion, so the top is fixed and only the subtree below might still need work.

WHY does it terminate? Each swap moves the value strictly down one level. A tree of $n$ nodes is only about $lo g_{2} n$ levels tall, so at most $lo g_{2} n$ swaps.

PICTURE. Watch value $3$ at seat $2$ : its children are $8$ and $2$ . Larger child is $8$ , so $3$ and $8$ swap; $3$ lands at a leaf, done.

Step 4 — Build the heap from the bottom up

WHAT. We repair small subtrees first, then bigger ones, so that whenever we sift a node, its children's subtrees are already proper heaps — exactly the precondition Step 3 required.

WHY bottom-up and not top-down? If you fixed the root first, its children could still be a mess, so you would have to keep re-fixing. Building upward means every fix is final.

The trace (heap size $n = 7$ throughout):

Call	Node	Action	Array after
`sift(2)`	$3$	swap with child $8$	$[4, 10, 8, 5, 1, 3, 2]$
`sift(1)`	$10$	already $\geq 5, 1$ — no swap	$[4, 10, 8, 5, 1, 3, 2]$
`sift(0)`	$4$	swap with $10$ ; then $4$ vs $5, 1$ → swap with $5$	$[10, 5, 8, 4, 1, 3, 2]$

PICTURE. The finished max-heap: $10$ has floated to the top, every red edge from Step 2 is now green.

Step 5 — Crown the champion, exile it to the back

WHAT. Swap $A [0]$ (the $10$ ) with $A [6]$ (the $2$ ). Now $10$ is in its final resting place. Reduce the live heap size from $7$ to $6$ .

WHY it works. Seat $0$ is guaranteed to hold the current maximum (Step 2). Placing maxima at the back, one at a time, from largest inward, is literally selection sort — but selection made cheap by the heap.

The damage. After the swap, the small value $2$ now sits at the root and violates the heap property. But its two subtrees are still perfect heaps → precondition for sift-down holds. One sift-down(0, size=6) repairs it.

PICTURE. Blue = the frozen sorted zone growing from the right; the heap shrinks on its left.

Step 6 — Repeat until the heap is empty

WHAT. Do Step 5 over and over: swap root to the last live seat, shrink, sift-down the root. Each pass freezes one more value into the sorted zone.

WHY $n - 1$ times and not $n$ ? When only one live element remains, it is trivially the smallest and already in place — no work needed. So the loop runs from end = n-1 down to 1.

The full drain (each row: state after crowning + re-heapifying):

Pass	Crown to back	Heap size now	Array (│ = sorted wall)
1	$10$	6	$[8, 5, 3, 4, 1, 2 │ 10]$
2	$8$	5	$[5, 4, 3, 2, 1 │ 8, 10]$
3	$5$	4	$[4, 2, 3, 1 │ 5, 8, 10]$
4	$4$	3	$[3, 2, 1 │ 4, 5, 8, 10]$
5	$3$	2	$[2, 1 │ 3, 4, 5, 8, 10]$
6	$2$	1	$[1 │ 2, 3, 4, 5, 8, 10]$

Result: $[1, 2, 3, 4, 5, 8, 10]$ — sorted, and we never used a second array.

PICTURE. The blue sorted wall marching leftward, one crown per pass.

Step 7 — Edge and degenerate cases

The one-picture summary

The array becomes a tree (Step 1), the tree becomes a heap by bottom-up sifting (Steps 3–4), then each pass crowns the top value into the growing sorted zone and re-heapifies (Steps 5–6) — all inside the one original array.

Recall Feynman retelling — say it like a story

Imagine seven kids in a bracket. First I arrange them into a triangle where every coach beats both players under them — I do this from the bottom coaches upward so each fix sticks (that's build heap). Now the overall champion is standing at the very top. I shake their hand and walk them to the last empty chair on the right — that chair is now theirs forever. I pull a random kid up to the top to replace them, and they sink down until the "coach beats players" rule holds again. Champion, chair, sink. Champion, chair, sink. Each time the right-hand row of taken chairs grows leftward, and the tournament shrinks. When one kid is left, they're already the smallest and sit down on their own. The chairs, left to right, now read smallest to largest — and I never needed a second room. Because I re-run a full mini-tournament after every crowning, it always costs about $n lo g n$ handshakes, sorted-input or not — and because the champion sometimes leaps over an equal-ranked kid, ties can swap order, which is why heap sort is not stable.

Recall Quick self-test

Left child of seat $i$ ::: seat $2 i + 1$ Where does the max sit in a max-heap ::: seat $0$ (the root) First node we sift when building a heap of size $n$ ::: seat $⌊ n /2 ⌋ - 1$ Time complexity in the best case ::: still $O (n lo g n)$ Is heap sort stable ::: no — crown-swaps move equal keys apart