subroute.
Advanced10 min readlive prototype

Heap Sort

Pour the array into a max-heap, then repeatedly pull the largest off the top. O(n log n) worst-case, in-place, no recursion.

Overview

What this concept solves

Heap sort is the algorithm with the most reassuring promise of any comparison sort: O(n log n) on every input, in-place. No quicksort-style adversarial pivot. No merge sort-style O(n) extra memory. Heap sort gives you both guarantees at once, and the price is a slightly worse constant factor than quicksort on random data.

The trick is the binary heap data structure: an array we interpret as a complete binary tree, with the rule that every parent ≥ its children (a max-heap). Parent of index i is (i-1)/2; children are 2i+1 and 2i+2. With that one structural invariant, the largest value always sits at index 0.

Sorting becomes a two-phase job. Build phase: turn the array into a max-heap with a single bottom-up sweep — O(n), surprisingly. Sort phase: repeatedly swap the root (max) to the end, shrink the heap by one, and sift-down the new root to re-establish the heap property. Each sift is O(log n) and we do n of them. n log n total, in-place, predictable, and no recursion at all if you're careful.

Mechanics

How it works

The heap, as an array

  1. Treat a[0] as the tree root.
  2. For any index i: left child is at 2i + 1, right child at 2i + 2, parent at (i - 1) / 2 (integer division).
  3. Max-heap invariant: a[parent(i)] >= a[i] for every i ≥ 1.
  4. Consequence: a[0] is the global maximum, always.

sift-down(i, size)

  1. Look at i's children (within size). Pick the larger of the two (or the only one if there's just one).
  2. If that child is bigger than a[i], swap and recurse into the child's slot.
  3. Otherwise stop — the invariant holds.

Build phase — O(n)

  1. Loop i from (n / 2) - 1 down to 0 — every non-leaf index, in reverse.
  2. For each i, call sift-down(i, n).
  3. Bottom-up beats top-down by an order: most calls only sift a few levels, and the math works out to O(n) total, not O(n log n).

Sort phase — O(n log n)

  1. Swap a[0] (current max) with a[size - 1].
  2. Decrement size — the just-locked max is no longer part of the heap.
  3. sift-down(0, size) to restore the invariant on the smaller heap.
  4. Repeat until size == 1. Now the array is sorted ascending.

Why building a heap is O(n), not O(n log n)

Bottom-up build does sift-down at every non-leaf. Most non-leaves are near the bottom and only sift down a few levels. The sum across levels is n/2 · 1 + n/4 · 2 + n/8 · 3 + … which converges to ≈ 2n. Top-down build (insert one at a time) would be O(n log n) — a real and avoidable cost.

Heap sort isn't stable

The big swap-root-with-end step jumps an equal-keyed value past arbitrarily many others. If you need stability, mergesort or Timsort are the comparison-sort options.

Interactive prototype

Run it. Break it. Tune it.

Sandboxed simulation embedded right in the page. No setup, no install.

About this simulation

The array becomes a binary tree on top; the heap is built by sifting parents down (Phase: Build), then the root (max) is repeatedly swapped to the end and the heap shrinks (Phase: Sort). Press Play, Step / Back to walk each compare-and-swap, Shuffle for a new list.

Hands-on

Try these on your own

Open the prototype above, run each experiment, predict the answer, then verify.

try 01

Play through the two phases

Press Play. Watch the Phase stat switch from Build to Sort. In Build, parents sift down to establish the max-heap. In Sort, the root (always the current max) swaps with the last heap slot, the heap shrinks, and the new root sifts down. After n-1 iterations of Sort, the array is sorted.

try 02

Watch a sift-down

Use Step until you see a purple focus node with two orange children. Step once more — the focus compares against its children, picks the bigger, and swaps if needed. The focus walks down the tree until it lands on a node that's bigger than both its children.

try 03

See the array-as-tree mapping

The tree at the top and the bar row beneath show the same data. Index 0 is the root, 1 and 2 are its children, 3–6 are the grandchildren. Every parent in the tree should be at least as tall as its children when the heap invariant holds. After Build phase, scan visually: every parent ≥ children.

try 04

Shuffle and compare comparisons

Press Shuffle and step through. On a random 7-element input, expect about 12 comparisons in Build phase and another 30+ in Sort phase. Total stays near n log n regardless of how scrambled the input is — no best case, no worst case, same work either way.

In practice

When to use it — and what you give up

When it's the right tool

  • Hard worst-case guarantees — embedded systems, real-time controllers, anywhere you can't afford an O(n²) outlier.
  • Memory-constrained sorting — in-place, no extra buffer, no recursion stack if you write it iteratively.
  • As introsort's fallback — once quicksort detects recursion blowing up, it switches to heap sort to finish in O(n log n).
  • Priority queues — the heap itself is the structure behind std::priority_queue, Python's heapq, Dijkstra and A* open-sets.

When to reach for something else

  • You want maximum in-memory speed on random data — quicksort wins on constants by ~2×.
  • You need stability — heap sort isn't stable; mergesort and Timsort are.
  • You're sorting nearly-sorted data — heap sort doesn't adapt; Timsort exploits existing runs.
  • The data is integers in a small range — counting / radix beat O(n log n) entirely.

Pros

  • Guaranteed O(n log n) on every input — no worst-case landmine.
  • In-place — O(1) extra memory; the heap lives inside the input array.
  • No recursion if implemented iteratively — predictable stack usage.
  • The heap is independently useful — same code powers Dijkstra, A*, top-k queries, and event-loop schedulers.

Cons

  • Slower than quicksort on random data — worse cache behaviour because parent-to-child jumps skip around in memory.
  • Not stable — equal-keyed elements can be reordered by the big swap.
  • Doesn't adapt — sorted input still takes full O(n log n).
  • Less educational than merge sort for divide-and-conquer; the heap data structure is the real concept to learn.

Reference

Code & further reading

A minimal reference implementation and pointers worth bookmarking.

heap-sort.ts
// Heap sort — in-place, O(n log n) on every input, not stable.
function heapSort<T>(a: T[]): T[] {
  const n = a.length;
  // Phase 1: build max-heap bottom-up (O(n), not O(n log n)).
  for (let i = (n >> 1) - 1; i >= 0; i--) siftDown(a, i, n);
  // Phase 2: pull the max to the end, shrink, re-heapify.
  for (let end = n - 1; end > 0; end--) {
    [a[0], a[end]] = [a[end], a[0]];
    siftDown(a, 0, end);
  }
  return a;
}

function siftDown<T>(a: T[], i: number, size: number): void {
  while (true) {
    const l = 2 * i + 1, r = 2 * i + 2;
    let largest = i;
    if (l < size && a[l] > a[largest]) largest = l;
    if (r < size && a[r] > a[largest]) largest = r;
    if (largest === i) break;
    [a[i], a[largest]] = [a[largest], a[i]];
    i = largest;
  }
}

// Example
heapSort([12, 11, 13, 5, 6, 7]);
// → [5, 6, 7, 11, 12, 13]

References & further reading

6 sources

Knowledge check

Did the prototype land?

Quick questions, answers revealed on submit. No scoring saved.

question 01 / 03

Why is the build-heap phase O(n) and not O(n log n)?

question 02 / 03

Where does heap sort's structure show up outside of sorting?

question 03 / 03

In std::sort (C++ standard library), what role does heap sort play?

0/3 answered

Was this concept helpful?

Tell us what worked, or what to improve. We read every note.

Back to Sorting