Heap Sort

How it works, step by step

1. 1

   View the array as a tree: the value at position i has children at positions 2i+1 and 2i+2. No pointers needed.

2. 2

   Build a max-heap: starting from the last parent and going backwards, sift down every node - swap it with its bigger child until it is bigger than both.

3. 3

   Now the biggest value of the whole array is at position 0.

4. 4

   Swap it with the last value of the heap. The big value is now in its final place - shrink the heap by one so it is never touched again.

5. 5

   The new root is probably in the wrong place - sift it down to restore the heap.

6. 6

   Repeat swap-and-sift until the heap is empty. Each round costs log n, so the total is n log n.

The code, in JavaScript

function heapSort(arr) {
  const a = [...arr];
  const n = a.length;

  // Phase 1: build a max-heap, from the last parent backwards.
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    siftDown(a, i, n);
  }

  // Phase 2: pull the max out, again and again.
  for (let end = n - 1; end > 0; end--) {
    [a[0], a[end]] = [a[end], a[0]];  // max goes to its final slot
    siftDown(a, 0, end);              // repair the shrunken heap
  }

  return a;
}

function siftDown(a, i, size) {
  for (;;) {
    const left = 2 * i + 1;
    const right = 2 * i + 2;
    let biggest = i;

    if (left < size && a[left] > a[biggest]) biggest = left;
    if (right < size && a[right] > a[biggest]) biggest = right;
    if (biggest === i) return;        // parent already wins - done

    [a[i], a[biggest]] = [a[biggest], a[i]];
    i = biggest;                      // keep sinking
  }
}

heapSort([5, 1, 4, 2]);              // → [1, 2, 4, 5]

Dry run: sorting [5, 1, 4, 2]

The same steps the visualizer plays, written as a table. Generated by running the real algorithm - not written by hand.

• Building the heap is O(n), not O(n log n) - the classic interview trap. Most nodes are near the bottom and sift only a step or two; the math sums to linear time.
• Start heapify at `Math.floor(n / 2) - 1`, the last parent. Starting at n−1 wastes time on leaves; starting at 0 and going forward is simply wrong (children are not heaps yet).
• The children of i are at 2i+1 and 2i+2 only when the heap starts at index 0. Textbook pseudocode often starts at 1 with children at 2i and 2i+1 - mixing the two conventions is a very common source of broken heaps.
• After swapping the max to the end, sift down within the shrunken size (`end`), not the full array - otherwise the sorted tail gets pulled back into the heap.

Heap Sort vs. its closest relatives