Heapsort

Overview

Property	Value
Best Case	$O(n)$
Worst Case	$O(n\lg n)$
Avg. Case	$O(n\lg n)$
Aux. Memory	$O(1)$
Stable	No
Adaptive	Yes

void heapsort(int n, int H[static n]) {
  build_max_heap(n, H);
  while (n > 1) {
    swap(A, 0, --n);
    max_heapify_down(n, A, 0);
  }
}

Refer to heaps for implementations of build_max_heap and max_heapify_down.

Loop Invariant

Consider loop invariant $P$ given by

A[0:i-1] is a max-heap containing the i smallest elements of A. A[i:n-1] contains the n - i largest elements of A sorted.

We prove $P$ maintains the requisite properties:

• Initialization
  • A[0:n-1] is a max-heap and A[n:n-1] is empty.
• Maintenance
  • On each iteration, A[0] is swapped with A[i-1]. A[0] is originally the largest element of the max-heap and is smaller than the elements of A[i:n-1]. Thus A[i-1:n-1] is in sorted order. Decrementing i, decrementing the heap size, and invoking MAX_HEAPIFY_DOWN on A[0] fixes the max-heap property of A[0:i-1].
• Termination
  • We terminate when i = 1. Since A[0:1] is a max-heap, it follows A[0] < A[1]. Furthermore, A[2:n-1] are the largest n - 2 elements of A in sorted order. Thus A is sorted.

Bibliography

• “Heapsort.” In Wikipedia, April 27, 2024. https://en.wikipedia.org/w/index.php?title=Heapsort&oldid=1220986714.
• Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022).