Heap sort treats the array as a binary tree stored flat: the children of index i
live at 2i + 1 and 2i + 2. It first builds a max-heap so the largest value
sits at the root, then repeatedly swaps the root to the end and sifts the new root
down to fix the heap. Each extraction shrinks the heap by one and grows the sorted
suffix by one.
Press play to watch both phases, or step through one comparison at a time. Orange is the pair being compared, yellow is a swap in progress, and green is locked in its final position.
Ready. 12 values, unsorted.
0 comparisons · 0 swaps
Ready. 12 values, unsorted.
- Comparing
- Swapping
- Sorted
Code
- def heap_sort(a):
- n = len(a)
- for i in range(n // 2 - 1, -1, -1):
- sift_down(a, n, i)
- for end in range(n - 1, 0, -1):
- a[0], a[end] = a[end], a[0]
- sift_down(a, end, 0)
- return a
- def sift_down(a, size, i):
- largest = i
- left = 2 * i + 1
- right = 2 * i + 2
- if left < size and a[left] > a[largest]:
- largest = left
- if right < size and a[right] > a[largest]:
- largest = right
- if largest != i:
- a[i], a[largest] = a[largest], a[i]
- sift_down(a, size, largest)
Try Reversed to see heap sort handle a descending array without any performance
penalty — it is always O(n log n), unlike quick sort which degrades on sorted
inputs.
Time and space complexity
| Case | Complexity | Why |
|---|---|---|
| Best | O(n log n) | The heap must still be fully built and dismantled, even if the input is sorted. |
| Average | O(n log n) | Each of the n extractions sifts down through at most log n levels. |
| Worst | O(n log n) | No adversarial input exists. The tree is always balanced. |
| Space | O(1) | Sorts in place. Only a temporary for swaps. |
| Stable | No | The extract-and-sift process does not preserve relative order of equal values. |
The guaranteed O(n log n) worst case is what sets heap sort apart from quick sort. No pivot choice can make it quadratic.
Step by step
- Build the max-heap. Starting from the last non-leaf node (index
⌊n/2⌋ − 1), sift each node down so every parent is larger than its children. This takes O(n) total because most nodes are near the bottom and sift very little. - Extract the maximum. Swap the root (index 0, the largest) with the last unsorted position. That value is now in its final place.
- Restore the heap. The new root probably violates the heap property, so sift it down through the reduced heap.
- Repeat steps 2–3 until only one element remains.
Worked example
Sorting [4, 10, 3, 5, 1]:
| Step | Array | What happened |
|---|---|---|
| Build heap | [10, 5, 3, 4, 1] | Sift from index 1: 10 > 4 stays. Sift from index 0: 10 > 4 stays. Max-heap ready. |
| Extract 1 | [5, 4, 3, 1, 10] | Swap 10 to end. Sift root 1 down → 5, 4, 3, 1. |
| Extract 2 | [4, 1, 3, 5, 10] | Swap 5 to position 3. Sift root 1 down → 4, 1, 3. |
| Extract 3 | [3, 1, 4, 5, 10] | Swap 4 to position 2. Sift root 1 down → 3, 1. |
| Extract 4 | [1, 3, 4, 5, 10] | Swap 3 to position 1. One element left, done. |
Five values, four extractions. Each sift walks at most two levels of the tree.
When to use it
| Reach for it when | Avoid it when |
|---|---|
| You need a guaranteed O(n log n) worst case | You want a stable sort — use merge sort |
| Memory is tight and you cannot afford merge sort's O(n) buffer | Cache performance matters and you can tolerate quick sort's rare worst case |
| You are building a priority queue and already have a heap | The input is nearly sorted — insertion sort does that in O(n) |
| You need a selection algorithm (find the k largest values) | You need the simplest code — bubble sort is shorter to teach |
The code
Both phases — build-heap and extract — share the same sift_down helper. The
build phase runs it bottom-up; the extract phase runs it on the root after each
swap.
def heap_sort(a):
n = len(a)
def sift_down(size, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < size and a[left] > a[largest]:
largest = left
if right < size and a[right] > a[largest]:
largest = right
if largest != i:
a[i], a[largest] = a[largest], a[i]
sift_down(size, largest)
# Build max-heap
for i in range(n // 2 - 1, -1, -1):
sift_down(n, i)
# Extract elements one by one
for end in range(n - 1, 0, -1):
a[0], a[end] = a[end], a[0]
sift_down(end, 0)
return a
nums = [4, 10, 3, 5, 1]
heap_sort(nums)
print(nums)
Common questions
What is the time complexity of heap sort?
O(n log n) in the best, average and worst case. Building the heap is O(n), and each of the n extractions costs O(log n) for the sift-down. Unlike quick sort, heap sort never degrades to O(n²).
Is heap sort stable?
No. When the root is swapped to the end and sifted down, equal values can end up in a different relative order from their original positions.
Why is it called heap sort?
Because the algorithm relies on the heap data structure — a complete binary tree stored in an array where every parent is at least as large as its children (max-heap). The sorting happens by repeatedly removing the root of the heap.
How does heap sort compare to quick sort?
Both are O(n log n) on average, but quick sort is usually faster in practice because it has better cache locality and a smaller constant factor. Heap sort's advantage is its guaranteed O(n log n) worst case — quick sort can degrade to O(n²) on adversarial inputs without randomisation.
What is the space complexity of heap sort?
O(1) auxiliary space. The heap is built in place within the input array, and only a constant number of temporary variables are needed for swapping.
How does the array represent a binary tree?
For any element at index i, its left child is at 2i + 1 and its right child is at 2i + 2. The parent of index i is at floor((i − 1) / 2). This implicit structure means no pointers are needed.