vizlearn
Home / Algorithms

Heap Sort

Algorithms & Data StructuresBy Updated

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: heapify for i in range(n//2-1, -1, -1): sift_down(a, i, n) # phase 2: extract for 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)
Space O(1)
Stable No

Overview

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.

Before the details

That worst-case guarantee is its strongest property. Quicksort averages O(n log n) but degrades to O(n²) on adversarial input.

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.

Its position among the O(n log n) sorts

 Heap sortQuick sortMerge sort
Worst caseO(n log n)O(n²)O(n log n)
Extra spaceO(1)O(log n) stackO(n)
StableNoNoYes
Cache behaviourPoorExcellentGood
Typical speedSlowest of the threeFastestMiddle

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

  1. Watch phase 1. Sifting starts from the middle of the array, never the leaves — that is why heapify is O(n).
  2. 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.

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:

ComponentProvides
Quick sortSpeed in the common case
Heap sortThe O(n log n) worst-case guarantee
Insertion sortLow 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.

Sources and next steps

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
Output
How the code works
  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.




Predict, then reveal
About to run: set array size to its maximum (14). Before it does — what happens to the readout?
Committing to an answer first is the point — the reveal runs the experiment on the visualisation above and reads the real value back, so nothing here is scripted.
Check yourself
0 of 3
Answer without scrolling back up.
  1. After the heapify phase, the list is:
  2. Building the heap bottom-up, starting at the last parent, costs:
  3. Why does the extraction phase swap the root with the last item?





 Cheat sheet
Heap Sort
Build a max-heap and extract the largest element n times for a guaranteed O(n log n) sort — no worst case, no extra memory.
ALGORITHMS · vizlearn.in/dsa/heap_sort.html
More in Algorithms
AlgorithmsTrie (Prefix Tree)AlgorithmsUnion-Find (Disjoint Set)AlgorithmsGraph RepresentationsAlgorithmsBreadth First Search
About the author
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.
About VizLearnGitHubLinkedInContact