Heap Sort Algorithm Explained

Heap sort builds a max-heap from the data, then repeatedly removes the largest element from the top and rebuilds the heap, producing a sorted list.

Published November 15, 2026

Heap sort builds a max-heap from the data, then repeatedly swaps the root (largest) to the end and restores the heap on the remainder. It sorts in place in guaranteed O(n log n).

The concept

Phase 1 heapifies the array in O(n). Phase 2 extracts the maximum n times, each costing O(log n) to sift down.

It uses no extra memory and has no bad case, but it is not stable and has poorer cache behaviour than quicksort.

Extract the max repeatedly

  1. Build a max-heap: [9, 7, 8, 3, 5]
  2. Swap root with last → [5, 7, 8, 3, 9], heap size 4
  3. Sift down to restore the heap: [8, 7, 5, 3 | 9]
  4. Repeat until the heap is empty

Practical examples

JavaScript

function heapSort(a) {
  a = [...a]
  const sift = (i, n) => { for (;;) { let m = i, l = 2*i+1, r = l+1
    if (l < n && a[l] > a[m]) m = l
    if (r < n && a[r] > a[m]) m = r
    if (m === i) return; [a[i], a[m]] = [a[m], a[i]]; i = m } }
  for (let i = (a.length >> 1) - 1; i >= 0; i--) sift(i, a.length)
  for (let end = a.length - 1; end > 0; end--) { [a[0], a[end]] = [a[end], a[0]]; sift(0, end) }
  return a
}

Python with heapq

import heapq
heapq.heapify(a)
sorted_a = [heapq.heappop(a) for _ in range(len(a))]

Complexity

O(n log n) always · O(1) extra space · not stable

Common mistakes

  • Mixing min-heap and max-heap order.
  • Sifting beyond the heap boundary.
  • Expecting stability.

Key takeaways

  • Heapify, then extract max repeatedly.
  • O(n log n) guaranteed, in place.
  • Not stable.

FAQ

Heap sort vs quicksort?

Heap sort has a better worst case; quicksort is usually faster in practice.

Where is it used?

As the fallback in introsort and in memory-tight systems.

More General articles