Heap Sort

Heap sort combines the O(n log n) guarantee of merge sort with the O(1) extra space of quicksort. It does this by exploiting the max-heap data structure, where the largest element is always at the root. If you are not yet familiar with heaps, think of a max-heap as an array where arr[i] >= arr[2*i+1] and arr[i] >= arr[2*i+2] — the parent is always at least as large as its children.

Two-Phase Algorithm

Phase 1 — Build a max-heap. Starting from the last non-leaf node and working backward to the root, call heapifyDown on each node. This rearranges the array into heap order in O(n) time (not O(n log n) — a non-obvious but important fact).

Phase 2 — Extract maximum n − 1 times. The maximum is always arr[0]. Swap it with the last element of the heap, shrink the heap boundary by one, and call heapifyDown on the new root to restore the heap property. After n − 1 extractions the array is sorted in ascending order.

JavaScript Implementation

function heapifyDown(arr, n, i) {
  let largest = i;
  const left = 2 * i + 1;
  const right = 2 * i + 2;

  if (left < n && arr[left] > arr[largest]) largest = left;
  if (right < n && arr[right] > arr[largest]) largest = right;

  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    heapifyDown(arr, n, largest);
  }
}

function heapSort(arr) {
  const n = arr.length;

  // Phase 1: build max-heap (start from last non-leaf)
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapifyDown(arr, n, i);
  }

  // Phase 2: extract elements one by one
  for (let i = n - 1; i > 0; i--) {
    // Move current root (maximum) to end
    [arr[0], arr[i]] = [arr[i], arr[0]];
    // Restore heap property for the reduced heap
    heapifyDown(arr, i, 0);
  }

  return arr;
}

console.log(heapSort([12, 11, 13, 5, 6, 7]));
// => [5, 6, 7, 11, 12, 13]

Why It Is Not Stable

The swap between arr[0] and arr[i] in Phase 2 can move an element far from its original position. Two equal elements may be reordered relative to each other during this process, so heap sort is not stable.

Cache Locality

Heap sort’s practical weakness is cache performance. The heapifyDown procedure accesses elements at indices i, 2i+1, and 2i+2, which for large arrays fall in very different cache lines. Quicksort and merge sort both access memory more sequentially, giving better cache utilisation. This is why heap sort, despite its theoretical guarantees, is rarely faster than randomised quicksort on real hardware.

Complexity

When to Use It

Heap sort is valuable when you need a guaranteed O(n log n) worst case without any extra memory — something quicksort cannot offer. Introsort (used in C++ STL) switches from quicksort to heap sort whenever the recursion depth exceeds 2 log n, capturing the best of both worlds.

Up Next

Counting sort breaks the O(n log n) barrier entirely by abandoning comparisons in favour of counting element frequencies — at the cost of requiring bounded integer keys.