Heaps & gaps · Intermediate
Heap Sort
Build a max-heap, then repeatedly move its root maximum to the sorted suffix.
- Best
- O(n log n)
- Average
- O(n log n)
- Worst
- O(n log n)
- Space
- O(1)
- Stability
- Not stable
- Memory model
- In-place
How it builds order
- Turn the array into a max-heap.
- Swap the root with the last unsorted item.
- Shrink the heap.
- Sift the new root down to restore heap order.
Why it works
The heap root is always the maximum, so each extraction places the next-largest value permanently.
Watch for: Array indexes encode a tree: children of i are 2i + 1 and 2i + 2.
The interactive version of this page adds the full trace, synchronized pseudocode, practice decisions, input experiments, and mastery review.