Heap Sort Explained: Binary Heaps, Code & Complexity

Heap sort turns the array into a binary max-heap — a complete binary tree where every parent is at least as large as its children — and then repeatedly removes the maximum, placing it at the end of the array. The result is a guaranteed O(n log n) sort that runs in place with O(1) extra memory, combining merge sort’s worst-case guarantee with quick sort’s low memory use.

New to heaps? Read Heaps: Introduction first — it explains the array-as-tree layout that heap sort relies on.

The idea

A binary heap is stored in a plain array: the children of index i are at 2i + 1 and 2i + 2. The algorithm has two phases:

Build a max-heap from the unordered array (bottom-up heapify). The largest element ends up at index 0.
Sort-down: swap the root (the max) with the last element, shrink the heap by one, and siftDown the new root to restore the heap property. Repeat until the heap is empty. Each extracted max lands in its final sorted position at the back.

The key helper is siftDown(i): if a node is smaller than its largest child, swap them and continue downward until the heap property holds.

Implementation

void siftDown(std::vector<int>& a, int i, int n) {
    while (true) {
        int largest = i, l = 2 * i + 1, r = 2 * i + 2;
        if (l < n && a[l] > a[largest]) largest = l;
        if (r < n && a[r] > a[largest]) largest = r;
        if (largest == i) break;
        std::swap(a[i], a[largest]);
        i = largest;
    }
}

void heapSort(std::vector<int>& a) {
    int n = (int)a.size();
    for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, i, n); // build heap
    for (int end = n - 1; end > 0; end--) {
        std::swap(a[0], a[end]);  // max to the back
        siftDown(a, 0, end);      // restore on the shrunk heap
    }
}

void siftDown(int[] a, int i, int n) {
    while (true) {
        int largest = i, l = 2 * i + 1, r = 2 * i + 2;
        if (l < n && a[l] > a[largest]) largest = l;
        if (r < n && a[r] > a[largest]) largest = r;
        if (largest == i) break;
        int t = a[i]; a[i] = a[largest]; a[largest] = t;
        i = largest;
    }
}

void heapSort(int[] a) {
    int n = a.length;
    for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, i, n); // build heap
    for (int end = n - 1; end > 0; end--) {
        int t = a[0]; a[0] = a[end]; a[end] = t; // max to the back
        siftDown(a, 0, end);                     // restore on the shrunk heap
    }
}

function siftDown(a, i, n) {
  while (true) {
    let largest = i;
    const l = 2 * i + 1, r = 2 * i + 2;
    if (l < n && a[l] > a[largest]) largest = l;
    if (r < n && a[r] > a[largest]) largest = r;
    if (largest === i) break;
    [a[i], a[largest]] = [a[largest], a[i]];
    i = largest;
  }
}

function heapSort(a) {
  const n = a.length;
  for (let i = (n >> 1) - 1; i >= 0; i--) siftDown(a, i, n); // build heap
  for (let end = n - 1; end > 0; end--) {
    [a[0], a[end]] = [a[end], a[0]]; // max to the back
    siftDown(a, 0, end);             // restore on the shrunk heap
  }
}

def sift_down(a, i, n):
    while True:
        largest = i
        l, r = 2 * i + 1, 2 * i + 2
        if l < n and a[l] > a[largest]:
            largest = l
        if r < n and a[r] > a[largest]:
            largest = r
        if largest == i:
            break
        a[i], a[largest] = a[largest], a[i]
        i = largest

def heap_sort(a):
    n = len(a)
    for i in range(n // 2 - 1, -1, -1):  # build heap
        sift_down(a, i, n)
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]      # max to the back
        sift_down(a, 0, end)             # restore on the shrunk heap

Complexity

Case	Time
Best	O(n log n)
Average	O(n log n)
Worst	O(n log n)

Build-heap is O(n) (a tighter bound than the obvious O(n log n)); the sort-down phase is O(n log n), which dominates.
Space: O(1) — fully in-place, no recursion needed (the loops above are iterative).
Stable: no — sifting moves elements across long distances and reorders equal keys.

Going deeper: Building a max-heap for ascending order can feel backwards. The reason: extracting the max and placing it at the back fills the array right-to-left, leaving ascending order.

When to use it

When you want a guaranteed O(n log n) with O(1) extra space and don’t need stability — for example in memory-constrained environments, or as the fallback inside introsort (which quick sort uses to escape its O(n²) worst case). In practice it is often slower than quick sort due to poor cache locality (it jumps around the array), so it is more a safety net than a first choice. See the comparison page. The same heap structure powers priority queues.

Next: Counting & Radix Sort.