Heap Sort

Heap sort is a comparison-based sorting algorithm that reorganizes the array into a max-heap — a complete binary tree where every parent is at least as large as its children — then repeatedly swaps the root maximum to the end and repairs the heap. It runs in O(n log n) time in every case and uses O(1) extra space.

The trick that makes it possible: any array already is a complete binary tree. Slot 0 is the root and the children of slot i live at 2i + 1 and 2i + 2 — pure index arithmetic, no pointers, no allocation. Once you see the tree hiding in the row, the algorithm is a machine that eats the array from the right: the heap region shrinks one slot per extraction while the sorted tail grows to meet it.

How Heap Sort Works

Both phases share one workhorse, sift_down: compare a node with the larger of its children, swap downward if that child wins, repeat until the heap property holds. A node can fall at most the height of the tree, so one sift costs at most ⌊log₂ n⌋ swaps.

Phase 1 — build. Walk the parents backwards, from the last parent ⌊n/2⌋ − 1 to the root, sifting each down. Bottom-up order means every subtree below the current node is already a valid heap, so one pass suffices. Counterintuitively, the whole phase costs only O(n) — most nodes sit near the bottom with almost no room to fall.

Phase 2 — sort. For end = n − 1 down to 1: swap the root (the maximum of what remains) with arr[end], shrink the heap so that slot becomes final, and sift the new root down inside the smaller heap. Each extraction is one swap plus a log-depth sift.

Heap Sort Step by Step

The default input is [38, 12, 56, 7, 41, 23, 5], n = 7.

Build phase. The last parent is ⌊7/2⌋ − 1 = 2 (value 56); its children 23 and 5 are smaller, so it is already settled. Parent i = 1 (value 12): the larger child is 41, and 41 > 12, so they swap; 12 lands on a leaf, settled. Array: [38, 41, 56, 7, 12, 23, 5]. Parent i = 0 (value 38): the larger child is 56, swap; 38's new children 23 and 5 are smaller, settled. The max-heap stands at [56, 41, 38, 7, 12, 23, 5] with the maximum on the root, three sift calls and two swaps after we started.

Extraction 1. Swap root 56 with arr[6] = 5; slot 6 is final and the heap-sorted divider appears. Now 5 sits on the root of a 6-slot heap and must earn its depth: 41 is the larger child — swap; then 12 beats 5 — swap again. Two levels of sinking, the ⌊log₂ n⌋ cost made visible. Heap: [41, 12, 38, 7, 5, 23], sorted tail [56].

Extractions 2 through 6 repeat the rhythm — one swap to the boundary, one shrink, a short sift — finalizing 41, then 38, then 23, then 12, then 7. Each sift in this run is at most one swap deep. The last survivor, 5, is necessarily the minimum and is already in slot 0. Result: [5, 7, 12, 23, 38, 41, 56].

The animation draws both views of the same array at once — circles in a tree (the view of meaning) and cells in a row (the view of storage) — and every swap moves in both simultaneously. Watch the heap | sorted divider step left exactly one slot per extraction; the green tail to its right never reorders again. Then try the input 56, 41, 38, 23, 19, 12, 7: a reverse-sorted array is already a max-heap, so the entire build phase performs zero swaps.

Time and Space Complexity

Build-heap alone is O(n); the n − 1 extractions at log cost each dominate. These are upper bounds, not the work every input does: a sift stops as soon as the parent is no smaller than its children, so an all-equal array finishes in linear time. The animated version is the standard in-place form — bottom-up build, then extract — with an iterative sift_down.

Heap sort's bargain is unusual: unlike quick sort it has no bad input (the heap's height bounds every sift, so no input pushes it past O(n log n)), and unlike merge sort it needs no auxiliary array. What it gives up: stability — equal values pass each other during the long root-to-end swaps — and cache friendliness, since 2i + 1 jumps scatter across memory while its rivals stream through it. That last point is why quick sort usually wins the benchmarks anyway.

Edge Cases

• Empty or one-element array — both loops run zero times.
• Reverse-sorted input — already a max-heap: zero build swaps, but the extraction phase still does its full work. Heap sort is not adaptive.
• Already-sorted input — roughly the opposite: small values sit near the root and must sink far during build.
• Duplicates — the strict > comparison means ties never trigger swaps, but equal values can still end up reordered by extractions; heap sort is not stable.

Common Mistakes

• Building top-down. Sifting parents from the root downward fails — a child subtree that is not yet a heap can feed a wrong value upward. Start at ⌊n/2⌋ − 1 and walk backwards.
• Forgetting to shrink the heap. Calling sift_down(arr, n, 0) instead of sift_down(arr, end, 0) after the swap drags already-sorted values back into play.
• Sifting toward one fixed child. The parent must swap with the larger of its two children; always taking the left one breaks the heap on the other side.
• Off-by-one in the index math. Zero-based children are 2i + 1 and 2i + 2; using 2i quietly assumes a 1-based heap.
• Looping down to end = 0. The final element is necessarily the minimum; stopping at 1 is correct, and the extra iteration is pure waste.