Step 0 / 0 · Comparisons: 0 · Swaps: 0
How this algorithm works
How it works
- Treat the array as a binary tree: index i has children at 2i+1 and 2i+2.
- Starting from the last parent, sift each node down until it sits above its children.
- When the build phase ends, the largest value is at the root.
- Swap the root with the last unsorted slot — that position is now final.
- Sift the new root down through the shrunken heap.
- Repeat until only one unsorted element remains.
Key concepts
- Binary heap as an implicit tree over an array
- Two phases: build, then repeatedly extract
- In-place (O(1) extra space)
- Not stable — equal elements can be reordered by a swap
When to use it
When you need guaranteed O(n log n) with no extra memory. Quick sort is usually faster in practice, but its worst case is quadratic; heap sort has none.
Did you know
Heap sort never allocates: the heap lives inside the array being sorted, using index arithmetic instead of pointers.