Skip to content
ReadMe Daily

Search articles, problems, patterns and every cheat sheet topic.

Sorting

Heap Sort Visualiser

Build a max-heap inside the array, then take the top repeatedly.

Starting order

Read the array as a binary tree: the children of index i are at 2i+1 and 2i+2. Build a max-heap, then take the top repeatedly.

Comparisons
0
Writes
0
for scale
n log₂n ≈ 53
AverageO(n log n)extra space O(1)

The count sits at roughly twice the curve: every sift-down compares the two children with each other, then compares the winner with the parent. That constant is exactly what Big-O drops. The counter is an exact count for this run; the curve beside it is the shape that count follows as n grows, not a limit on it.

  • Being compared
  • Being written
  • Pivot or smallest so far
  • In its final place
  • Ruled out
function heapSort(a) {
for (let i = (a.length >> 1) - 1; i >= 0; i--) siftDown(a, i, a.length);
for (let end = a.length - 1; end > 0; end--) {
[a[0], a[end]] = [a[end], a[0]];
siftDown(a, 0, end);
}
return a;
}
function siftDown(a, i, size) {
while (true) {
const left = 2 * i + 1, right = left + 1;
let largest = i;
if (left < size && a[left] > a[largest]) largest = left;
if (right < size && a[right] > a[largest]) largest = right;
if (largest === i) return;
[a[i], a[largest]] = [a[largest], a[i]];
i = largest;
}
}

The highlighted line is the one that produced the picture on the left.

What Heap Sort does

Heap sort reads the array as a binary tree without building one: the children of index i live at 2i+1 and 2i+2. Arrange it so every parent is at least as big as its children — a max-heap — and the biggest value is at index 0. Swap that to the end, shrink the heap, repair it, repeat.

How it works, step by step

  1. Build the heap bottom-up: sift each internal node down until it is no smaller than its children.
  2. Swap the root, which is the largest value, with the last value in the heap.
  3. That position is now final, so shrink the heap by one.
  4. Sift the new root down to restore the heap, and repeat until one value is left.

What to watch for

  • Sifting always follows one path from a node to a leaf, and the tree is log₂n deep, so a single repair costs log n however big the array is.
  • The build phase is faster than it looks: most nodes are near the bottom and barely move. It is O(n) in total, not O(n log n).
  • The sorted region grows from the right, and values in the heap jump around a lot — which is why heap sort is not stable.

Cost

Best caseO(n log n)
AverageO(n log n)
Worst caseO(n log n)
Extra spaceO(1)
StableNo

When to reach for it

When memory is tight and the worst case matters: it is the only common sort that is both in place and guaranteed n log n. In practice quicksort is usually faster because heap sort jumps all over the array and misses the cache, so heap sort often appears as the fallback quicksort switches to when recursion gets too deep.

Read more