Heapsort

Algorithm

Heapsort sorts an array in two phases:

Phase 1: Build a max-heap from the input array in $O(n)$ time.

Phase 2: Repeatedly extract the maximum and place it at the end:

1. Build-Max-Heap($A$).
2. For $i = A.\text{length}$ down to 2:
3.  Swap $A[1]$ (the maximum) with $A[i]$.
4.  Decrement heap_size (excludes the sorted suffix).
5.  Max-Heapify($A$, 1).

After each iteration, $A[1 \dots i-1]$ is a max-heap and $A[i \dots n]$ contains the largest $n-i+1$ elements in sorted order. When $i$ reaches $2$, the entire array is sorted in ascending order (assuming a max-heap; for descending order, use a min-heap).

Walkthrough

Input: $[1, 9, 3, 4, 2, 7, 6, 5, 8]$

Phase 1 (Build-Heap): $[1, 9, 3, 4, 2, 7, 6, 5, 8] → [9, 8, 7, 5, 2, 3, 6, 1, 4]$ (max-heap)

Phase 2 (Extract-Max loop):
  i=9: swap 9 ⇄ 4, heapify → heap [8,5,7,1,2,3,6,4 | 9]
  i=8: swap 8 ⇄ 4, heapify → heap [7,5,6,1,2,3,4 | 8, 9]
  i=7: swap 7 ⇄ 4, heapify → heap [6,5,3,1,2,4 | 7, 8, 9]
  i=6: swap 6 ⇄ 4, heapify → heap [5,4,3,1,2 | 6, 7, 8, 9]
  i=5: swap 5 ⇄ 2, heapify → heap [4,2,3,1 | 5, 6, 7, 8, 9]
  i=4: swap 4 ⇄ 1, heapify → heap [3,2,1 | 4, 5, 6, 7, 8, 9]
  i=3: swap 3 ⇄ 1, heapify → heap [2,1 | 3, 4, 5, 6, 7, 8, 9]
  i=2: swap 2 ⇄ 1, heapify → heap [1 | 2, 3, 4, 5, 6, 7, 8, 9]

Final: [1, 2, 3, 4, 5, 6, 7, 8, 9]

Complexity Analysis

Phase 1 (Build-Max-Heap): $\Theta(n)$ as proved earlier.

Phase 2: $n-1$ iterations, each calling Max-Heapify on the root of a shrinking heap. Max-Heapify on a heap of size $k$ costs $O(\log k)$. Summing:

$T(n) = \Theta(n) + \sum_{k=2}^{n} O(\log k) = \Theta(n) + O(\log(n!))$

Using Stirling’s approximation: $\log(n!) \le n \log n - n + O(\log n)$. Therefore:

$T(n) = O(n \log n)$

This bound is worst-case. Heapsort never degrades to $\Theta(n^2)$, unlike Quicksort.

In-Place Property

Heapsort uses only $O(1)$ extra space beyond the input array (a few variables for indices and the temporary for swaps). The heap is stored within the same array as the sorted output, separated by the heap_size boundary. This is achieved by using the suffix of the array for the sorted region and the prefix for the heap.

Cache Performance

Heapsort’s in-place nature comes at a cost: Max-Heapify jumps between array positions at powers of 2 ($i \to 2i \to 4i \to \dots$), which are far apart in memory for large indices. This results in poor cache locality compared to Quicksort (which scans contiguously during partitioning) and MergeSort (which merges contiguously). In practice, Heapsort is often slower than Quicksort for moderate $n$, despite its superior worst-case guarantee.

Comparison with Other Sorts

Sort	Worst Case	Average Case	In-place	Stable
Heapsort	$O(n \log n)$	$O(n \log n)$	Yes	No
MergeSort	$\Theta(n \log n)$	$\Theta(n \log n)$	No ($\Theta(n)$)	Yes
Quicksort	$\Theta(n^2)$	$\Theta(n \log n)$	Yes	No
Insertion Sort	$\Theta(n^2)$	$\Theta(n^2)$	Yes	Yes

Summary

Phase	Cost	Description
Build-Heap	$\Theta(n)$	Bottom-up max-heapify
Extract loop	$O(n \log n)$	$n-1$ extractions, each $O(\log k)$
Total	$O(n \log n)$	Worst-case guarantee
Space	$O(1)$	In-place via array prefix/suffix split
Stable	No	Swaps non-adjacent elements
Cache	Poor	Non-local memory access pattern
Advantage	Good worst case, in-place
Disadvantage	Slower constant factors, poor cache