Heap Sort Visualization

Heap Sort builds a max-heap from the list, then repeatedly moves the largest value to the end.

How it works

Heap Sort first arranges the array as a binary max-heap: every parent is at least as large as its children, so the largest value sits at the front. It then swaps that largest value to the end of the array, shrinks the heap by one, and sifts the new front value down until the heap property holds again. Repeating this fills the array from the back with the largest values.

Every sift-down follows one path from the root to a leaf, about log n steps, so the whole sort is n log n in every case and needs no extra memory. In practice it is slower than Quick Sort because it jumps around the array, which caches dislike, and it is not stable.

What to watch for

Watch the array turn into a loose, rough order first (that's the heap), then the sorted section grows from the end one value at a time.

Complexity

Best

n log n

Average

n log n

Worst

n log n

Extra space

1

Stable

No

Race it

Same shuffle, same speed, one winner: Heap vs Merge. Or open the studio to try other layouts, sizes and speeds, and make a video of it.

FAQ