Heapsort

Heapsort is selection sort with a better way of selecting. Selection sort scans the unsorted region to find its maximum in $O(n)$; heapsort keeps that region as a heap so the maximum is at the root and extraction costs $O(\log n)$. That single substitution converts $O(n^2)$ into $O(n \log n)$.

Its distinguishing property is the combination no other common sort offers: $O(n \log n)$ worst case in $O(1)$ space. Mergesort needs a buffer; quicksort has a quadratic worst case; heapsort has neither problem.

Two phases. First the array becomes a heap; then the root is repeatedly swapped to the end, shrinking the heap and growing the sorted tail. Wikimedia Commons, CC BY-SA 3.0

Core Concepts

Property	Value
Best case	$O(n \log n)$
Average	$O(n \log n)$
Worst case	$O(n \log n)$ — guaranteed
Space	$O(1)$ — genuinely in place, no recursion
Stable	No
Adaptive	No — sorted input costs the same as random

Mechanism

The array is used as both the heap and the output. The heap occupies a shrinking prefix; the sorted result grows as a suffix behind it.

Python

def heapsort(a):
    n = len(a)

    # Phase 1: build a max-heap in place — O(n), not O(n log n)
    for i in range(n // 2 - 1, -1, -1):
        sift_down(a, i, n)

    # Phase 2: repeatedly move the max to the end and shrink the heap
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]     # largest element to its final position
        sift_down(a, 0, end)            # restore the heap over the remaining prefix
    return a

def sift_down(a, i, size):
    while True:
        largest = i
        for child in (2 * i + 1, 2 * i + 2):
            if child < size and a[child] > a[largest]:
                largest = child
        if largest == i:
            return
        a[i], a[largest] = a[largest], a[i]
        i = largest

C++

#include <cassert>
#include <functional>
#include <queue>
#include <utility>
#include <vector>

void sift_down(std::vector<int>& a, int i, int size) {
    for (;;) {
        int largest = i;
        for (int child : {2 * i + 1, 2 * i + 2})
            if (child < size && a[child] > a[largest]) largest = child;
        if (largest == i) return;
        std::swap(a[i], a[largest]);
        i = largest;
    }
}

void heapsort(std::vector<int>& a) {
    int n = static_cast<int>(a.size());

    // Phase 1: build a max-heap in place — O(n), not O(n log n)
    for (int i = n / 2 - 1; i >= 0; --i)
        sift_down(a, i, n);

    // Phase 2: repeatedly move the max to the end and shrink the heap
    for (int end = n - 1; end > 0; --end) {
        std::swap(a[0], a[end]);        // largest element to its final position
        sift_down(a, 0, end);           // restore the heap over the remaining prefix
    }
}

Phase 1 is $O(n)$ — see the heaps page for why building a heap is linear rather than n log n. Phase 2 does n extractions at $O(\log n)$ each, so it dominates: $O(n \log n)$ overall.

Using a max-heap rather than a min-heap is what makes the sort ascending: the largest element is swapped to the end, and each subsequent one lands just before it.

Tracing the first extraction on [5, 1, 8, 3]. Phase 1 builds the max-heap first (sift_down runs on index 1, then index 0):

Step	Action	Array
start	—	[5, 1, 8, 3]
build, i=1	children of 1 are just index 3 (3 > 1); swap a[1] ↔ a[3]	[5, 3, 8, 1]
build, i=0	children of 0 are 1, 2 (3, 8); 8 > 5, swap a[0] ↔ a[2]	[8, 3, 5, 1]

The array is now a valid max-heap: [8, 3, 5, 1]. Phase 2's first extraction swaps the root with the last live element, then sifts down over the heap shrunk by one:

Step	Action	Array	Heap size
extract 1	swap a[0] ↔ a[3] (8 ↔ 1)	[1, 3, 5, 8]	3
sift_down(0, 3)	children of 0 are 1, 2 (3, 5); 5 > 1, swap a[0] ↔ a[2]	[5, 3, 1, 8]	3
sift_down(2, 3)	index 2 has no children within size 3	[5, 3, 1, 8]	done

One extraction, one $O(\log n)$ sift-down, and the maximum (8) is now fixed at the end in its final sorted position — exactly like selection sort's swap-to-boundary step, but found in $O(\log n)$ instead of a full $O(n)$ scan.

Practical Usage

Heapsort is rarely the top-level choice, but it occupies two important roles:

• The safety net in introsort. C++'s std::sort runs quicksort, and switches to heapsort when recursion exceeds $2 \cdot \log_2 n$ levels. This makes the worst case $O(n \log n)$ without giving up quicksort's speed on typical input. Heapsort is chosen for the fallback precisely because it needs no extra memory and has no bad case of its own.
• Memory-constrained and real-time systems. Embedded and kernel contexts where an $O(n)$ allocation is unacceptable and an $O(n^2)$ tail is unacceptable. The Linux kernel's sort() is a heapsort.

Python

# Partial sorting: the top k without sorting everything — O(n + k log n)
import heapq
def top_k(items, k):
    heap = list(items)
    heapq.heapify(heap)                       # O(n)
    return [heapq.heappop(heap) for _ in range(k)]   # k × O(log n)

C++

// Partial sorting: the top k without sorting everything — O(n + k log n)
std::vector<int> top_k(std::vector<int> items, int k) {
    std::priority_queue<int, std::vector<int>, std::greater<>>
        heap(std::greater<>{}, std::move(items));          // heapify: O(n)
    std::vector<int> out;
    for (int i = 0; i < k && !heap.empty(); ++i) {         // k x O(log n)
        out.push_back(heap.top());
        heap.pop();
    }
    return out;
}

Stopping phase 2 after k extractions gives the k largest elements in $O(n + k \log n)$ — better than a full sort when k is small, which is the same argument behind heapq.nlargest.

Python

# checked on the traced input
assert heapsort([5, 1, 8, 3]) == [1, 3, 5, 8]
assert heapsort([]) == []

C++

int main() {
    std::vector<int> a{5, 1, 8, 3};
    heapsort(a);
    assert((a == std::vector<int>{1, 3, 5, 8}));
}

Edge Cases & Pitfalls

Heapsort is the slowest $O(n \log n)$ sort in practice

Its complexity is excellent and its constant factor is not. sift_down jumps between indices i, 2i+1 and 2i+2 — locations that grow exponentially far apart, so each level of a sift is a fresh cache miss. Quicksort's partition scans memory sequentially and mergesort's merges are also sequential; heapsort's access pattern is nearly the worst possible.

On typical in-memory arrays it commonly runs 2–3× slower than quicksort despite identical asymptotic complexity. Choose it for its guarantees, not for its speed.

• n // 2 - 1 is the last internal node. Starting the build loop anywhere else either wastes work on leaves or leaves part of the heap unbuilt.
• sift_down must be bounded by size, not len(a) — otherwise phase 2 sifts back into the already-sorted suffix and corrupts it.
• It is not stable, and equal elements are reordered by the long-distance swaps.
• A min-heap sorts descending. If you want ascending output, build a max-heap.

Comparisons

	Heapsort	Quicksort	Mergesort	Selection
Worst case	$O(n \log n)$	$O(n^2)$	$O(n \log n)$	$O(n^2)$
Space	$O(1)$	$O(\log n)$	$O(n)$	$O(1)$
Stable	No	No	Yes	No
Locality	Poor	Excellent	Good	Good
Typical speed	Slowest of the three	Fastest	Good	Very slow
Choose when	Guarantees + no memory	Default for arrays	Stability or external sort	Writes are costly

Recall

InvariantThe array is split into a shrinking heap prefix and a growing sorted suffix; each extraction moves the heap's root (the current maximum) to the front of the sorted suffix and restores the heap property over what remains.

Costs

build-heap phase (worst)$O(n)$

one extraction + sift-down (worst)$O(\log n)$

full sort, best/average/worst$O(n\log n)$

extra space (worst)$O(1)$

Reach for itAn $O(n\log n)$ worst-case guarantee is required in $O(1)$ space — no allocation allowed, and no quadratic tail allowed either. This is exactly introsort's fallback role.

TrapBounding sift_down by the array's full length instead of the current (shrinking) heap size. It then sifts back into the already-sorted suffix and corrupts elements that were already in their final position.

References

• Williams, J.W.J. (1964), "Algorithm 232: Heapsort", Communications of the ACM — the original, which introduced the heap along with it.
• Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, 4th ed., Ch. 6 — heapsort with the $O(n)$ build-heap proof.
• Linux kernel lib/sort.c — a production heapsort, with comments on why it was chosen.

Books & Videos

• VisuAlgo — Sorting — the two phases are much clearer watched than read.

Related Pages

• Heaps & Priority Queues — the structure this is built on.
• Selection Sort — the same algorithm with a linear scan instead of a heap.
• Choosing a Sort — introsort, where heapsort is the fallback.