Heap Sort
Builds a max-heap, then repeatedly extracts the largest element to the end.
- Comparisons 0
- Swaps 0
- sorted indices 0
- compare
- swap
- sorted
Heap (tree view)
Pseudocode
1 buildMaxHeap(a)
2 for i from n - 1 downto 1
3 swap a[0], a[i]
4 heapSize = heapSize - 1
5 siftDown(0)
6 siftDown(i)
7 l = 2i + 1; r = 2i + 2
8 largest = i
9 if l < heapSize and a[l] > a[largest]: largest = l
10 if r < heapSize and a[r] > a[largest]: largest = r
11 if largest != i
12 swap a[i], a[largest]
13 siftDown(largest)
Step log
How it works, runtime and memory
Heap Sort treats the array as a binary tree: the element at index i has its children at indices 2i+1 and 2i+2. The first phase builds a max-heap by calling siftDown on every internal node from bottom up: the element is compared with the larger of its children and swapped down as long as a child is larger. After the build the maximum sits at the root (index 0). The second phase repeatedly swaps the root with the last heap element, shrinks the heap by one (the swapped element is now considered sorted) and restores the heap property by sifting down the new root. This continues until the heap is empty. The heap build costs O(n) and the n-1 sift-downs cost O(log n) each, producing the guaranteed total runtime O(n log n) in every case. Heap Sort runs in-place (O(1) extra memory) but is not stable.
Complexity
- Best case
O(n log n) - Average case
O(n log n) - Worst case
O(n log n) - Extra space
O(1)
When to use it
First choice when the worst case must stay guaranteed at O(n log n) and no extra memory is available, because Heap Sort runs fully in-place. Suitable for embedded and real-time systems and serves as the safety net inside Introsort when Quick Sort recurses too deep.