Heapsort
Medium+95 XPBuild a max-heap, then keep pulling the biggest off the top and parking it at the end. Guaranteed O(n log n), in place.
No visualization loaded.
Watch
—
Press Run to begin.
Heapsort borrows the heap's superpower: a max-heap always keeps the BIGGEST value on top. So sorting becomes a two-step dance. First, rearrange the array into a max-heap. Then repeatedly take the top value (the current maximum), swap it to the end of the array where it belongs, shrink the heap by one, and 'sift down' the new top to restore the max-heap rule. Each round locks one more value into its final place, so the sorted region grows from the right until the whole array is in order — and it all happens inside the same array.
▸How does heapsort use a heap to sort?
A max-heap guarantees the largest value is at the root (index 0). That's exactly the value that should go LAST in a sorted array. So you swap the root to the end, treat that slot as 'done', and re-heapify the smaller heap that's left. Repeat, and each time the next-largest value falls out of the top into its correct spot. The heap is just a machine for handing you the biggest remaining value, over and over.
▸Why a max-heap and not a min-heap?
Because we sort ascending IN PLACE, parking values at the end of the array as we go. The biggest value belongs at the very end, so we want the biggest on top to grab first — that's a max-heap. (You could use a min-heap, but then you'd build the sorted order at the front or end up sorting descending — max-heap keeps everything tidy with one shared array.)
▸Why is heapsort O(n log n) GUARANTEED, with no bad case like quicksort?
Building the heap is O(n). Then you do n extractions, and each one sifts a value down a tree of height about log n — so n × log n. Crucially, there's no 'unlucky pivot' to ruin it like in quicksort: the tree's height is always about log n no matter what the input looks like. So heapsort can never degrade to O(n²) — its worst case IS O(n log n).
▸Is heapsort in-place?
Yes. The heap lives inside the very same array you're sorting (using the 2i+1 / 2i+2 child rule — no real tree pointers). All the work is swaps within that array, and the recursion-free sift-down uses only a couple of variables. So heapsort needs O(1) extra space — even less than merge sort's O(n) temp buffer.
How the work grows
O(n log n) — always, even worst case is good — the practical sorting speed. Building the heap is O(n); then n extractions each sift a value down a height-log n tree → n×log n. The tree height is always ~log n regardless of input, so heapsort never degrades to O(n²) like quicksort can. It works inside the original array, so extra space is O(1).
Faint dotted lines = O(1) (flat) and O(n) (straight) for comparison.