Build a max-heap, then repeatedly swap the root to the end and re-sink. Guaranteed O(n log n) with O(1) extra space — the only common sort that gets both at once.
Controls
array size10
# phase 1: heapifyfor i in range(n//2-1, -1, -1):
sift_down(a, i, n)
# phase 2: extractfor i in range(n-1, 0, -1):
a[0], a[i] = a[i], a[0]
sift_down(a, 0, i)
Heap and Sorted Region
step 0
Insight
Two phases: heapify the array into a max-heap in O(n), then repeatedly swap the root to the sorted tail and sift down, n times at O(log n) each.
phase–
comparisons0
swaps0
extra memoryO(1)
Complexity
Time (all cases)O(n log n)
SpaceO(1)
StableNo
Heap Sort
The sort that never has a bad day — and never wins a benchmark either.
Before the details
Heap sort turns the array into a max-heap, then repeatedly moves the largest element to the end. It sorts in place with a guaranteed O(n log n) in every case — best, average and worst.
Phase 1: Heapify in O(n)
Starting from the last non-leaf node and working backwards, sift each element down. Leaves are already valid heaps of size one, so half the array needs no work at all.
It looks like it should be O(n log n), but it is O(n). Most nodes are near the bottom and can only sink a short distance; only the root can travel the full height. Summing the actual work gives a series that converges to O(n).
Phase 2: Extract n Times
The maximum is always at index 0. Swap it with the last element of the heap, shrink the heap by one, and sift the new root down to restore the heap property.
The array splits into two regions: an unsorted heap at the front and a growing sorted tail at the back. Watch the green region grow from the right as you step.
Each extraction costs O(log n) and there are n of them → O(n log n). Adding the O(n) heapify leaves O(n log n) overall.
Why It Loses to Quick Sort in Practice
Heap sort has better worst-case guarantees than quick sort (which can degrade to O(n²)) and uses less memory than merge sort (which needs O(n)). Yet quick sort is usually faster in the real world.
The reason is cache locality. Sifting jumps between indices i, 2i+1 and 2i+2 — wildly scattered addresses that defeat the CPU cache. Quick sort scans contiguously and stays cache-friendly. Heap sort also does more swaps and is not stable.
Its real niche is guaranteed worst-case behaviour with constant memory — embedded and real-time systems. It also appears inside introsort (used by C++'s std::sort), which starts with quick sort and switches to heap sort if recursion gets too deep, capping the worst case.
Selection sort with a better data structure
Heap sort has a clean derivation: selection sort repeatedly finds the largest remaining element, and finding it by scanning is O(n). A heap finds it in O(log n).
Same algorithm, better structure, and the complexity drops from O(n²) to O(n log n).
Two phases:
Build a max-heap from the array, in place, in O(n). Repeatedly swap the root (the maximum) with the last unsorted element, shrink the heap by one, and sift the new root down.
def heap_sort(arr):
n = len(arr)
for i in range(n // 2 - 1, -1, -1): # build the heap: O(n)
sift_down(arr, i, n)
for end in range(n - 1, 0, -1): # extract: n times O(log n)
arr[0], arr[end] = arr[end], arr[0] # max to its final position
sift_down(arr, 0, end) # restore the heap, excluding the tail
return arr
def sift_down(arr, i, size):
while True:
largest, left, right = i, 2*i + 1, 2*i + 2
if left < size and arr[left] > arr[largest]:
largest = left
if right < size and arr[right] > arr[largest]:
largest = right
if largest == i:
return
arr[i], arr[largest] = arr[largest], arr[i]
i = largest
Note that everything happens in the original array: the heap occupies the front, the sorted region grows from the back, and no auxiliary storage is needed.
Building the heap is O(n), not O(n log n)
A detail that surprises people and is worth understanding.
Sifting down from the middle backwards looks like n/2 operations each costing O(log n), suggesting O(n log n). The actual bound is O(n), because most nodes are near the bottom and have almost no distance to sift.
Half the nodes are leaves and need no work. A quarter are one level up and sift at most once. An eighth sift at most twice. Summing that series gives O(n).
Building by repeated insertion instead is O(n log n) — each insertion sifts up from a leaf, and the last insertions travel the full height. So the direction matters: sift down from the middle, not up from insertions.
Its position among the O(n log n) sorts
Heap sort
Quick sort
Merge sort
Worst case
O(n log n)
O(n²)
O(n log n)
Extra space
O(1)
O(log n) stack
O(n)
Stable
No
No
Yes
Cache behaviour
Poor
Excellent
Good
Typical speed
Slowest of the three
Fastest
Middle
Heap sort is the only one with both a guaranteed O(n log n) and O(1) extra space. That combination is unique among the classical sorts, and it is why the algorithm survives.
It is also the slowest of the three in practice, and the reason is cache behaviour: sifting jumps between indices i, 2i+1 and 2i+2, which on a large array means touching memory pages far apart. Quick sort's partitioning scans sequentially, which modern CPUs handle far better.
So heap sort is rarely chosen on its own — and it is chosen as a fallback, which is a genuinely important role.
Exploration guide
Watch phase 1. Sifting starts from the middle of the array, never the leaves — that is why heapify is O(n).
Note when the heap is valid. Every parent now beats its children, but the array is far from sorted — a heap is only partially ordered.
Watch phase 2. Each swap sends the current maximum to its final position and the green sorted region grows leftward.
Compare the tree and the array. They are the same data — the tree is drawn from array indices, with no pointers anywhere.
Shuffle and re-run. The operation counts barely move; heap sort has no bad inputs, unlike quick sort.
Where that leaves you
Heap sort is O(n log n) in every case with O(1) extra memory — the only common sort offering both. It loses on speed to quick sort because scattered sift-down accesses wreck cache locality, and it is not stable. Use it when worst-case guarantees matter more than raw throughput.
Introsort: where heap sort actually runs
C++'s std::sort is introsort, and heap sort is its safety net.
The algorithm starts with quick sort. It tracks recursion depth, and if the depth exceeds roughly 2 log n — evidence that pivots are being chosen badly and the O(n²) case is developing — it switches to heap sort for that subarray. Below a small threshold it finishes with insertion sort.
The result combines all three strengths:
Component
Provides
Quick sort
Speed in the common case
Heap sort
The O(n log n) worst-case guarantee
Insertion sort
Low overhead on small subarrays
That is heap sort's real production role: it is never the fastest choice, and it is the one that makes quick sort's worst case impossible. Without it, std::sort would have no guarantee.
Python takes a different route — Timsort, which is a stable merge sort — because Python guarantees stability and heap sort is not stable.
Why it is not stable
Sifting swaps elements that are far apart in the array, so equal elements can be reordered relative to their original positions.
Sorting [3a, 3b, 1] as a max-heap: 3a becomes the root, is swapped with the last element, and 3b ends up before it. The two equal values have exchanged order.
Making it stable requires attaching original indices as a tiebreaker, which needs O(n) extra space — and that removes the in-place advantage that was the reason to choose heap sort.
So heap sort's guarantee is worst-case time and constant space, never stability. When stability matters, merge sort or Timsort is the answer.
Related uses of the same structure
The heap itself is far more widely used than heap sort:
Priority queues in Dijkstra's algorithm, A*, and any scheduler.
Top-k selection. A min-heap of size k gives the k largest of n items in O(n log k) time and O(k) space — better than sorting everything when k is small. This is what heapq.nlargest does.
Partial sorting. Stopping heap sort after k extractions gives the k largest elements in sorted order, in O(n + k log n).
k-way merging. A heap of the front elements of k sorted streams merges them efficiently, which is how external sorting combines runs.
Running medians. Two heaps — a max-heap of the lower half and a min-heap of the upper — give the median of a stream in O(log n) per element.
Why building the heap is O(n), not O(n log n)
The claim that heapify costs O(n) looks wrong -- there are n elements and each sift is O(log n) -- and it is the one part of heap sort worth checking rather than accepting. Count the sift steps and the answer falls out of the shape of the tree.
example_01.pyPython
def sift_down(a, start, end, stats):
root = start
while 2 * root + 1 <= end:
child = 2 * root + 1
if child + 1 <= end:
stats["comps"] += 1
if a[child] < a[child + 1]:
child += 1
stats["comps"] += 1
if a[root] < a[child]:
a[root], a[child] = a[child], a[root]
stats["moves"] += 1
root = child
else:
return
def build_heap_bottom_up(a, stats):
a = a[:]
for start in range(len(a) // 2 - 1, -1, -1):
sift_down(a, start, len(a) - 1, stats)
return a
def build_heap_by_insertion(a, stats):
# the naive alternative: push one at a time, sifting UP each time
heap = []
for x in a:
heap.append(x)
i = len(heap) - 1
while i > 0:
parent = (i - 1) // 2
stats["comps"] += 1
if heap[parent] < heap[i]:
heap[parent], heap[i] = heap[i], heap[parent]
stats["moves"] += 1
i = parent
else:
break
return heap
import random
print("%8s %14s %14s %10s" % ("n", "bottom-up", "by insertion", "n log2 n"))
for n in (15, 31, 63, 127, 255, 511):
data = random.Random(4).sample(range(n * 3), n)
b = {"comps": 0, "moves": 0}
i = {"comps": 0, "moves": 0}
build_heap_bottom_up(data, b)
build_heap_by_insertion(data, i)
print("%8d %14d %14d %10d" % (
n, b["comps"], i["comps"], int(n * (n.bit_length() - 1))))
# The bottom-up column grows in step with n, not with n log n: look at the
# ratio as n doubles -- it is close to 2, while n log2 n grows faster.
#
# The reason is where the elements are. In a heap of n nodes, half are
# leaves and sift down zero levels. A quarter sit one level up and can
# move at most one. An eighth can move at most two. The total is
# n * sum(k / 2^k), and that sum converges to 2 -- so the work is bounded
# by 2n however large the tree gets.
print()
print("%5s %10s %12s %12s" % ("level", "nodes", "max sift", "product"))
n = 255
total = 0
level, nodes, height = 0, (n + 1) // 2, 7
while nodes >= 1:
product = nodes * level
total += product
print("%5d %10d %12d %12d" % (height - level, nodes, level, product))
nodes //= 2
level += 1
print("total sift steps bounded by %d, and 2n = %d" % (total, 2 * n))
# Building by repeated insertion has the opposite shape: it sifts UP, so
# an element entering at the bottom can travel the whole height, and the
# many nodes are the ones with the furthest to go. On random input that
# costs a modest premium -- most insertions stop early because the value
# is not large. The gap opens up when the input is ascending, because then
# every new element is the largest so far and climbs all the way to the
# root:
print()
print("%8s %14s %14s" % ("n", "bottom-up", "by insertion"))
for n in (63, 255, 1023):
ascending = list(range(n))
b = {"comps": 0, "moves": 0}
i = {"comps": 0, "moves": 0}
build_heap_bottom_up(ascending, b)
build_heap_by_insertion(ascending, i)
print("%8d %14d %14d" % (n, b["comps"], i["comps"]))
# Bottom-up does not notice; insertion pays the full log n per element.
# Same data structure, same n -- the difference is which end of the tree
# the many nodes are at, and which direction the algorithm walks.
Output
Questions people ask
Why is heap sort slower than quick sort if both are O(n log n)? Cache behaviour. Sifting jumps between distant indices; quick sort scans sequentially.
Is it stable? No, and making it stable requires extra space, which defeats its purpose.
Why is building the heap O(n)? Most nodes are near the leaves and sift a short distance; the series sums to O(n).
Where is it used in practice? As introsort's fallback, providing the worst-case guarantee behind quick sort's speed.
Max-heap or min-heap for ascending order? Max-heap — the largest goes to the end of the array first.
Can it sort in place? Yes, and that is its distinguishing feature: O(1) extra space with a guaranteed O(n log n).
Recap in one screen
Build a max-heap in O(n), then repeatedly swap the root to the end and sift down.
Building by sifting down from the middle is O(n); building by repeated insertion is O(n log n).
Uniquely among classical sorts: guaranteed O(n log n) and O(1) extra space.
Slower than quick sort in practice because sifting has poor cache locality, and not stable.
Its production role is introsort's fallback, which is what gives std::sort its worst-case guarantee.
Run it in Python
Two phases, printed separately: build a max-heap out of the raw list, then repeatedly move the root to the end. Nothing is allocated — the heap and the sorted output share one list.
heap_sort.pyPython 3
# Heap sort: build a max-heap in place, then pull the maximum out n times.
def sift_down(a, root, end):
"""Push a[root] down until the subtree below it is a valid max-heap."""
while True:
child = 2 * root + 1 # left child
if child >= end:
return
if child + 1 < end and a[child + 1] > a[child]:
child += 1 # take the larger of the two children
if a[root] >= a[child]:
return # heap property already holds
a[root], a[child] = a[child], a[root]
root = child
def heap_sort(a):
a = a[:]
n = len(a)
# Phase 1 - heapify. Leaves are heaps already, so start at the last parent.
for start in range(n // 2 - 1, -1, -1):
sift_down(a, start, n)
print(f"heapify from {start}: {a}")
# Phase 2 - repeatedly swap the root to the end and shrink the heap.
print()
for end in range(n - 1, 0, -1):
a[0], a[end] = a[end], a[0]
sift_down(a, 0, end)
print(f"place {a[end]:>3} at index {end}: heap={a[:end]} sorted={a[end:]}")
return a
data = [4, 10, 3, 5, 1, 8, 2]
print("start :", data)
print()
print("sorted:", heap_sort(data))
Output
How the code works
child = 2 * root + 1The tree is only an idea — the list is the tree. Node i's children are at 2i+1 and 2i+2, so no pointers, and no node objects, are needed.
if a[root] >= a[child]: returnThe early exit. A sift stops as soon as the heap property holds, which is what keeps each one at O(log n) rather than always walking to a leaf.
for start in range(n // 2 - 1, -1, -1):Everything past n // 2 - 1 is a leaf, and a leaf is a valid heap on its own. Building bottom-up like this is O(n) — not O(n log n), which is the surprising part.
a[0], a[end] = a[end], a[0]The root is the largest remaining value, so it belongs at the end of the unsorted region. One swap both extracts it and puts it in final position.
sift_down(a, 0, end)end shrinks each round, so the same list holds a shrinking heap on the left and a growing sorted run on the right. That is why heap sort needs O(1) extra space.
Change one thing
Print a after phase 1 only. It is not sorted — a heap is a much weaker ordering than a sorted list, and that weakness is what makes it cheap to build.
Flip both comparisons in sift_down to build a min-heap. The output comes out descending.
Sort [3, 1, 3] and follow the two 3s. They swap order — heap sort is not stable, unlike merge sort.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.
Check yourself
0 of 3
Answer without scrolling back up.
After the heapify phase, the list is:
A heap only promises each parent beats its children. Nothing is claimed about siblings - and that weakness is why it can be built in O(n).
Building the heap bottom-up, starting at the last parent, costs:
Most nodes are near the leaves and sift down barely at all. The sum works out linear, which surprises people who expect n sifts of log n each.
Why does the extraction phase swap the root with the last item?
One swap does both jobs, which is how heap sort sorts in place. The heap then shrinks by one and is repaired with a single sift.
Cheat sheet
Heap Sort
Build a max-heap, then repeatedly swap the root to the end and re-sink. Guaranteed O(n log n) with O(1) extra space — the only common sort that gets both at once.
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.