6.6 Heap Sort

Heap sort derives order from a heap structure. It first builds a max-heap from the input array, then repeatedly extracts the maximum element and places it at the end of the array. The array itself stores the heap, so the algorithm runs in place.

Problem

You have an array A[0..n-1]. You want a sorting algorithm with guaranteed $O(n \log n)$ time, constant extra space, and no dependence on input distribution.

Solution

Convert the array into a max-heap, then repeatedly swap the root with the last element and restore the heap property on the reduced range.

heap_sort(A):
  n = length(A)

  build_max_heap(A)

  for end = n - 1 down to 1:
    swap A[0] and A[end]
    sift_down(A, 0, end)

The function sift_down restores the heap property in the range [0, end).

sift_down(A, i, n):
  while true:
    left = 2*i + 1
    right = 2*i + 2
    largest = i

    if left < n and A[left] > A[largest]:
      largest = left

    if right < n and A[right] > A[largest]:
      largest = right

    if largest == i:
      break

    swap A[i] and A[largest]
    i = largest

Example

Start with:

[5, 2, 4, 1, 3]

First, build a max-heap:

[5, 3, 4, 1, 2]

Now extract the maximum element 5 and place it at the end:

[2, 3, 4, 1, 5]

Restore the heap property:

[4, 3, 2, 1, 5]

Repeat the process:

[1, 3, 2, 4, 5]
→ heapify → [3, 1, 2, 4, 5]
→ extract → [2, 1, 3, 4, 5]
→ extract → [1, 2, 3, 4, 5]

Heap Invariant

A max-heap satisfies:

For every index i:

A[i] ≥ A[left(i)]
A[i] ≥ A[right(i)]

where:

left(i) = 2*i + 1
right(i) = 2*i + 2

This invariant ensures that the maximum element is always at the root A[0].

Build Phase

The heap is built bottom-up by applying sift_down starting from the last internal node:

build_max_heap(A):
  n = length(A)
  for i = floor(n/2) - 1 down to 0:
    sift_down(A, i, n)

This process runs in linear time:

O(n)

Even though sift_down can take logarithmic time, most nodes are near the leaves and require very little work.

Sorting Invariant

At the start of each iteration of the extraction loop:

A[0..end] is a max-heap
A[end+1..n-1] is sorted

Each iteration removes the maximum element from the heap and places it into its final position at index end. The heap size decreases by one, and the sorted suffix grows by one.

When the loop finishes, the entire array is sorted.

Correctness

Heap sort satisfies the permutation condition because it only uses swaps.

It satisfies the order condition because each step places the largest remaining element into its final position. Since no later step moves elements from the sorted suffix back into the heap, the suffix remains sorted.

The heap property ensures that the root always contains the maximum of the current heap. Therefore extraction is correct at every step.

Complexity

Building the heap takes:

O(n)

Each extraction performs one swap and one sift_down, which takes:

O(log n)

There are n - 1 extractions, so total time is:

O(n log n)

The auxiliary space is:

O(1)

This makes heap sort one of the few algorithms with both $O(n \log n)$ worst-case time and constant extra memory.

Stability

Heap sort is not stable.

Swaps during heap construction and extraction move equal elements across the array without preserving their original order.

For example:

[(2, A), (1, B), (2, C)]

The result may be:

[(1, B), (2, C), (2, A)]

The relative order of equal keys is not preserved.

Implementation Notes

Heap sort is useful when:

memory must remain constant
worst-case guarantees are required
input distribution is unknown or adversarial

However, it often performs worse than quick sort in practice due to poor cache locality. Heap operations jump across the array, while quick sort scans sequentially.

Heap sort is also less adaptive. It performs the same work regardless of input order. A nearly sorted array does not reduce its runtime.

Common Bugs

A common bug is using incorrect child indices. Always verify:

left = 2*i + 1
right = 2*i + 2

Another bug is forgetting to reduce the heap size after each extraction. The sorted suffix must not be included in further heap operations.

A third bug is applying sift_down starting from the root only during heap construction. The correct build process must start from the last internal node and move upward.

Takeaway

Heap sort enforces global order through a heap invariant. It provides strong worst-case guarantees with minimal memory usage, at the cost of stability and cache efficiency.