What Is Heap Sort?

Heap Sort builds a max-heap from the array, then repeatedly moves the largest value (the root) to the back. It sorts in place with no extra array, yet always runs in O(n log n) regardless of input.

The one-line idea: "extract the max quickly and stack it from the back." A heap lets you see the max in O(1) and remove it in O(log n), so repeating that n times completes the sort.

First, a Heap Refresher

View the array as a complete binary tree. For index i:

•left child = 2i + 1, right child = 2i + 2
•parent = (i - 1) / 2

A max-heap follows the rule "every parent is ≥ its children," so the root (index 0) is always the overall maximum.

How It Works

Step 1. Build heap. Going backward from the last parent node down to index 0, apply sift-down (heapify) to each node to turn the whole array into a max-heap. This is O(n).

Step 2. Extract the max. Swap the root (arr[0]) with the heap's last element, sending the maximum to its final spot at the end of the array.

Step 3. Restore the heap. Shrink the heap size by one and run one sift-down from the root to restore the max-heap property.

Step 4. Repeat steps 2–3 until the heap size is 1. Large values pile up from the back, producing ascending order.

The AlgoNote visualization shows "build heap" and "extract & restore" as separate steps so the flow is clear at a glance.

Time and Space Complexity

Complexity
Time	O(n log n)
Space	O(1)

Building the heap is O(n); the following n extractions are O(log n) each, so the total is O(n log n). Like merge sort it always guarantees O(n log n), but it sorts in place with no extra array, so space is O(1).

Walking Through an Example

Turning [3, 1, 4, 1, 5] into a max-heap puts 5 at the root.

•Swap 5 with the last → 5 fixed at the end, restore → root 4
•Swap 4 with the second-to-last → ...4 5, restore → root 3
•Repeating yields [1, 1, 3, 4, 5]

Each round removes "the current heap's max," sorting from the back.

Common Mistakes

•sift-down vs up: when sinking the root during sorting, it's sift-down. Don't confuse it with insertion (sift-up).
•Heap size bookkeeping: re-including an already-extracted element (the sorted tail) in the heap range breaks the sort.
•Child index formula: skipping bounds checks on 2i+1/2i+2 reads past the array.

See It in Action on AlgoNote

Watch the array become a max-heap, the root move to the end, and the heap reorganize itself, step by step on AlgoNote.

Try the Heap Sort Visualization →