Sortingintermediatecomparisonin-placeheap

Heap Sort

Build a max-heap, then extract elements one by one.

How it works

Heap Sort works in two phases, both centred on the max-heap property: every parent node is greater than or equal to its children. In Phase 1 the algorithm transforms the raw array into a valid max-heap by calling heapify on every internal node from bottom to top — a process that takes O(n) time. Once the heap is built, arr[0] holds the largest element.

Phase 2 extracts elements in descending order. The root (largest) is swapped with the last element of the unsorted region, shrinking the heap by one and placing that element in its final sorted position. The new root is then sifted down through the reduced heap to restore the heap property. This extraction loop runs n−1 times, and each sift-down takes O(log n) work, giving O(n log n) total for the phase — and therefore O(n log n) overall in all cases.

Unlike Merge Sort, Heap Sort requires no extra memory beyond a few loop variables, making it an in-place O(1)-space algorithm. Unlike Quick Sort, its worst case is also O(n log n), so it provides absolute performance guarantees. The trade-off is poor cache behaviour: the sift-down operation accesses elements at indices 2i+1 and 2i+2, which are far apart for large heaps, leading to many cache misses compared to the sequential access patterns of merge sort or insertion sort.

Complexity

Best case

O(n log n)

Average case

O(n log n)

Worst case

O(n log n)

Space

O(1)

In-place

Visualizer

Generating steps…

Where it's used in the real world

Linux kernel — lib/sort.c

In-kernel sorting with guaranteed O(n log n) and zero allocation

The Linux kernel cannot call malloc during many critical paths. lib/sort.c implements heapsort because it provides O(n log n) worst-case performance with strictly O(1) auxiliary space — both properties are required in interrupt handlers and memory-constrained kernel contexts where dynamic allocation is forbidden.

C++ std::partial_sort

Retrieving the k smallest elements from a large collection

std::partial_sort builds a min-heap of size k over the first k elements, then sifts each remaining element through it. Because only k elements need to be sorted, the total cost is O(n log k) rather than O(n log n). This heap-based strategy is the standard implementation choice in libstdc++ and libc++.

Embedded and safety-critical systems

Deterministic sorting with bounded worst-case time and no allocation

In real-time systems (automotive ECUs, avionics, PLCs) algorithms must meet hard timing deadlines. Heap sort's O(n log n) worst-case guarantee — with no dynamic memory allocation and a small, fixed code footprint — makes it a reliable choice when predictability matters more than raw average-case speed.

Implementation

function heapSort(arr: number[]): number[] {
  const a = [...arr];
  const n = a.length;

  // Build max-heap
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(a, n, i);
  }

  // Extract elements one by one
  for (let i = n - 1; i > 0; i--) {
    [a[0], a[i]] = [a[i], a[0]];
    heapify(a, i, 0);
  }

  return a;
}

function heapify(arr: number[], size: number, root: number): void {
  let largest = root;
  const left = 2 * root + 1;
  const right = 2 * root + 2;

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

  if (largest !== root) {
    [arr[root], arr[largest]] = [arr[largest], arr[root]];
    heapify(arr, size, largest);
  }
}

// Usage
console.log(heapSort([38, 27, 43, 3, 9, 82, 10, 55]));
// [3, 9, 10, 27, 38, 43, 55, 82]

Related algorithms

Quick SortLive

Pick a pivot, partition around it, recursively sort partitions.

O(n log n)

Merge SortLive

Divide in half, sort each half recursively, merge back.

O(n log n)