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

This is the visual companion to Heap sort — in-place, O(n log n). If you have never seen a Binary Heap or a Complete Binary Tree, don't worry — we build every idea from zero right here.

---

Step 1 — An array is secretly a tree

WHAT. We start with six numbers in a plain list (an "array" — a row of boxes, each with a position number called its index, counted from $0$):

$A=[\underset{0}{\underbrace{3}},\underset{1}{\underbrace{1}},\underset{2}{\underbrace{6}},\underset{3}{\underbrace{5}},\underset{4}{\underbrace{2}},\underset{5}{\underbrace{4}}]$

The small number under each value is its index. Nothing is sorted yet.

WHY. Before we can "heapify" anything, we must see the array as a tree — a pyramid of nodes where each node can have two nodes hanging below it. We do this without moving any data: the tree is just a way of reading the same array.

The three rules that turn an index into a tree position — for a node at index $i$:

$\text{left child}=\underset{\text{skip past }i\text{’s row}}{\underbrace{2i+1}},\text{right child}=\underset{\text{one more}}{\underbrace{2i+2}},\text{parent}=\underset{\text{undo the doubling}}{\underbrace{\lfloor \frac{i-1}{2}\rfloor }}$

• $2i+1$ / $2i+2$: doubling the index jumps down one level of the pyramid; $+1$ and $+2$ pick the left vs right slot.
• $\lfloor \cdot \rfloor$ means "round down to a whole number" — it collapses both children back to the same parent.

PICTURE. Below, the flat array (top) is redrawn as a pyramid (bottom). Same numbers, same indices — just bent into a tree. The blue arrows show index $0$ reaching down to its two children at indices $1$ and $2$.

---

Step 2 — The rule we want: parent beats children (max-heap)

WHAT. We want the pyramid to obey one rule everywhere:

$A[\text{parent}]\ge A[\text{left child}]\text{AND}A[\text{parent}]\ge A[\text{right child}]$

Read $\ge$ as "is greater than or equal to". A tree obeying this everywhere is a max-heap.

WHY. If every parent outranks both its kids, then the single biggest number of all cannot be anyone's child — so it must be at the very top, index $0$. That is the whole trick: a max-heap always hands you its maximum for free.

PICTURE. Our starting tree violates the rule in several places (red edges = "child bigger than parent, illegal"). Green edges are already fine. We must fix every red edge.

Recall Why does "every parent ≥ children" force the max to the top?

Any node that is a child is $\le$ its parent, so it is not the maximum. The only node that is nobody's child is the root. Therefore the root holds the max. ::: The root is the only non-child, and everyone else is dominated by someone above them.

---

Step 3 — The one tool: sift-down (let a bad node sink)

WHAT. sift_down(i) fixes one node at index $i$, assuming the two subtrees below it are already valid heaps. It compares $A[i]$ with its two children, and if a child is bigger, swaps them — then repeats from the new position, following the value downward like a stone sinking in water.

WHY. We need a repeatable repair operation. Sifting down (not up) is right here because the node that is out of place is above correctly-ordered subtrees — the too-small value must travel down to its correct depth.

The comparison, term by term:

$\text{largest}=\max (\underset{\text{parent}}{\underbrace{A[i]}},\underset{\text{left}}{\underbrace{A[2i+1]}},\underset{\text{right}}{\underbrace{A[2i+2]}}),\text{skip any child index }\ge n$

Here $n$ is the current heap size; any index $\ge n$ is outside the heap and ignored (this is how leaves with only one — or zero — children are handled).

PICTURE. A value $3$ sitting on top of children $5$ and $4$ sinks: it swaps with the larger child $5$, moves down, checks again, and stops when both its new children are smaller. Yellow = the sinking node, red arrow = the swap taken.

---

Step 4 — Phase 1: build the heap from the bottom up

WHAT. We call sift_down on every internal (non-leaf) node, starting from the last internal node and walking backward to the root. The last internal node is at index

$\lfloor \frac{n}{2}\rfloor -1=\lfloor \frac{6}{2}\rfloor -1=2.$

So we sift index $2$, then $1$, then $0$.

WHY bottom-up? sift_down(i) demands that $i$'s subtrees already be valid heaps. By starting at the bottom and moving up, that precondition is always met: by the time we reach a node, everything beneath it was already fixed. Leaves (indices $>\lfloor n/2\rfloor -1$) are single nodes — already valid heaps — so we skip them entirely.

PICTURE. The three build steps on $[3,1,6,5,2,4]$:

• i = 2 (value $6$): children are $2$ and $4$, both smaller → no change.
• i = 1 (value $1$): children $5,2$ → swap with $5$ → array becomes $[3,5,6,1,2,4]$.
• i = 0 (value $3$): children $5,6$ → swap with $6$; then $3$ keeps sinking, swaps with child $4$ → array becomes $[6,5,4,1,2,3]$.

Final built max-heap: $[6,5,4,1,2,3]$ — the root is $6$, the true maximum. ✔

---

Step 5 — Phase 2: park the max at the back, shrink, repeat

WHAT. The root is the biggest number. Swap it with the last slot still in the heap, then pretend that last slot no longer belongs to the heap (shrink the heap size by one), then sift_down(0) to repair the new root.

$\underset{\text{max}}{\underbrace{A[0]}}⟷\underset{\text{last heap slot}}{\underbrace{A[\text{end}]}},\text{end}\text{ goes }n-1,n-2,\dots ,1$

WHY. Each swap drops the current maximum into its final, correct, sorted position at the right end — and it never moves again. The heap shrinks, the sorted tail grows. Because we always park the largest remaining value just left of the already-sorted part, the tail comes out in ascending order.

PICTURE. One extraction on $[6,5,4,1,2,3]$: swap $6\leftrightarrow 3$ → $[3,5,4,1,2,6]$; the $6$ (green) is now frozen. Heap size drops to $5$; sift the new root $3$ down (swaps with $5$) → $[5,3,4,1,2,6]$, a valid max-heap of size $5$ with $5$ on top.

---

Step 6 — Repeat until empty: the sorted region eats the heap

WHAT. Keep doing Step 5. Each round freezes one more value on the right. After $n-1$ rounds the heap has one element and the whole array is sorted.

WHY. After $k$ rounds, the $k$ largest values are locked in the rightmost $k$ slots, each in its final place. The leftover heap always keeps its "max on top" property, so the next round parks the next-largest correctly. Induction finishes the sort.

PICTURE. The full film strip for $[6,5,4,1,2,3]$ → sorted. The dividing line (yellow) between the shrinking heap (left) and the growing sorted tail (green) marches leftward, one slot per round.

Final array: $[1,2,3,4,5,6]$. ✔

---

Step 7 — Edge & degenerate cases (nothing left to surprise you)

WHAT. The cases the walkthrough must not skip:

• Empty array ($n=0$) or one element ($n=1$): the build loop range(n//2 - 1, -1, -1) runs zero times, and Phase 2's range(n-1, 0, -1) runs zero times. Nothing happens — a $0$- or $1$-element list is already sorted. ✔
• A node with only a left child. In the sift comparison, the right index $2i+2$ can be $\ge n$; we skip it. So a lone-child node compares against just its left child. This happens whenever $n$ is even (the last parent has one child).
• All equal keys, e.g. $[7,7,7,7]$: every comparison is a tie, no swap improves anything, so largest == i immediately and each sift stops instantly. Correct — but note the ties can still get swapped in Phase 2, which is exactly why heap sort is not stable.
• Already-sorted input $[1,2,3,4,5]$: still costs $O(n\log n)$. Heap sort has no "lucky" input — a virtue over Quicksort, whose worst case is $O(n^2)$.

WHY. These are precisely where naive code breaks: an out-of-bounds child read, or an infinite loop on ties. Our index guard l < n / r < n and our largest == i stop-condition cover every one.

PICTURE. Left: even-$n$ last parent with a single (left-only) child, right slot greyed out as "outside the heap". Right: the all-equal tree where no red edges ever appear.

---

The one-picture summary

Everything compressed: array→tree, build (bottom-up sifts), then $n-1$ rounds of swap-max-to-back → shrink → sift, with the sorted region (green) growing right-to-left.

Recall Feynman: tell the whole walkthrough to a friend

Line up your numbers in boxes. Pretend the row is a pyramid — box $0$ on top, its two kids just below, and so on (Step 1). We want a pyramid where every card beats the two cards under it, so the biggest card floats to the very top (Step 2). To make a bad card obey, we let it sink: swap it with its bigger child over and over until both its new kids are smaller (Step 3). We fix the whole pyramid by sinking every card, starting from the lowest parent and moving up, so the parts below are always already tidy (Step 4). Now the biggest card is on top — grab it and park it at the far right end, where it's done forever; shrink the pyramid to ignore that slot and sink the new top card to fix the rule (Step 5). Do that again and again: each round parks the next-biggest just left of the last, and the sorted stretch on the right grows until the pyramid is empty and the whole row is sorted (Step 6). And it never trips: empty rows, lone children, and all-equal cards are all handled by "ignore slots past the end" and "stop when nothing's bigger" (Step 7). No second table needed — that's the in-place magic.

Connections

• Binary Heap — the structure every picture here draws.
• Complete Binary Tree — why the array↔tree index arithmetic never has gaps.
• Priority Queue — same sift-down, used for live max/min access.
• Quicksort · Merge Sort · Introsort — the sorting cousins compared in the parent note.
• Big-O Notation — the language for the $O(n\log n)$ result derived here.