Heap Sort Explained
Heap Sort is special: it is the only comparison sort that guarantees O(n log n) time while using just O(1) extra space. It works by turning the array into a binary max-heap and then repeatedly extracting the maximum. That combination makes it valuable in memory-constrained and real-time systems.
The binary heap
A max-heap is a complete binary tree where every parent is greater than or equal to its children, cleverly stored in a plain array: the children of index i live at 2i+1 and 2i+2. The maximum is always at the root (index 0), which is what Heap Sort exploits.
How Heap Sort works
Build: turn the array into a max-heap using heapify from the bottom up — O(n). Sort: swap the root (the max) with the last element, shrink the heap by one, and sift the new root down to restore the heap property. Repeat. Each extraction places the next-largest value at the end, producing a sorted array.
Pseudocode
heapSort(a):
buildMaxHeap(a)
for end from n-1 down to 1:
swap(a[0], a[end])
siftDown(a, 0, end)Complexity and when to use it
Heap Sort is O(n log n) in all cases and O(1) space, but it is not stable and has poorer cache locality than Quick Sort (the parent-child jumps scatter memory access), so it is usually slower in practice. Use it when you need guaranteed worst-case performance with minimal memory, such as in real-time systems. It is also the fallback inside Introsort.
Frequently asked questions
What is the time complexity of Heap Sort? +
Is Heap Sort faster than Quick Sort? +
Why is Heap Sort used in Introsort? +
See it in motion
Watch this algorithm and 9 others run step by step in our free interactive visualizer.
▶ Launch Visualiser