Overview
Heap Sort turns the array into a binary max-heap, then repeatedly removes the maximum and places it at the end. It combines the O(n log n) guarantee of Merge Sort with the in-place property of Quick Sort.
How Heap Sort works
- Build a max-heap from the array so the largest element is at the root.
- Swap the root (maximum) with the last element of the heap.
- Shrink the heap by one and sift the new root down to restore the heap property.
- Repeat until the heap is empty; the array is now sorted ascending.
When to use it
- When you need O(n log n) worst-case time without Merge Sort's extra memory.
- Systems with tight memory budgets — it sorts fully in place.
- The same heap structure also powers priority queues.
Complexity analysis
Building the heap is O(n), and each of the n extractions costs O(log n) to sift down, so total time is O(n log n) in all cases. It is in-place (O(1) extra space) but not stable, and tends to be slower than Quick Sort in practice due to poor cache locality.
Frequently asked questions
If Heap Sort is O(n log n) and in-place, why isn't it the default?
Its jumps around the array hurt CPU cache performance, so Quick Sort is usually faster in practice. Heap Sort shines when the O(n log n) worst-case guarantee is non-negotiable.