I consider Heap Sort one of the most theoretically satisfying sorting algorithms I’ve studied, because it manages to combine two properties that usually seem to be in tension: guaranteed $O(n \log n)$ worst-case performance (something QuickSort can’t promise) and truly in-place sorting with only $O(1)$ auxiliary space (something Merge Sort can’t offer). It achieves this by building on the binary heap data structure I cover in my priority queue article, repurposing it directly as a sorting mechanism.
In this article, I want to give the complete picture of Heap Sort — how it works end to end, why it’s correct, and how it performs — while my two companion articles go deeper into its two internal phases: building a heap and maintaining the heap property.
History and Background
Heap Sort was invented by J.W.J. Williams in 1964, introduced in the same paper (Algorithm 232 – Heapsort, published in Communications of the ACM) that first described the binary heap data structure itself. I find it notable that the heap and Heap Sort were essentially co-invented — the data structure was designed specifically to enable this sorting algorithm.
Shortly after, in 1964, Robert W. Floyd published an improvement to the heap construction phase, showing that a heap could be built from an unsorted array in linear time, $O(n)$, rather than the $O(n \log n)$ that would result from inserting elements one at a time. This refinement — often called “Floyd’s build-heap algorithm” — is the version I implement and analyze in my dedicated article on building a heap, and it’s the version most modern textbooks (including CLRS) present as the standard approach.
Problem Statement
The problem I’m solving is the standard comparison-based sorting problem: given an array of $n$ elements, rearrange them into sorted order. What distinguishes Heap Sort’s approach is that it does this by first imposing a heap structure on the data, then repeatedly extracting the maximum element and shrinking the heap, which naturally produces sorted output when I place each extracted maximum at the end of the shrinking active region.
Core Concepts
- Max-heap: A complete binary tree (represented as an array) where every parent node’s value is greater than or equal to its children’s values, meaning the maximum element is always at the root.
- Heap size vs. array size: During Heap Sort, I distinguish between the full array size $n$ and the current “heap size,” which shrinks by one after each extraction, even though the underlying array stays the same size.
- Build-max-heap: The initial phase that transforms an arbitrary unsorted array into a valid max-heap.
- Heapify (sift-down): The repair operation that restores the heap property at a given node, assuming its subtrees are already valid heaps.
- In-place sorting: Heap Sort achieves sorting using only the original array plus a constant number of temporary variables — no auxiliary array is required.
How It Works
Here is the full sequence I follow for Heap Sort:
- Build a max-heap from the entire unsorted input array, using the bottom-up
buildMaxHeapprocedure (detailed in my companion article). - Swap the root of the heap (the maximum element, at index 0) with the last element in the current heap region.
- Reduce the heap size by one, effectively “removing” that last position from further heap operations — it now holds a correctly placed, sorted element.
- Restore the heap property at the new root (which is the element that used to be last) by calling
heapifyon index 0, using the reduced heap size. - Repeat steps 2–4 until the heap size is reduced to 1, at which point the entire array is sorted.
Working Principle
The internal logic here is a clever repurposing of the priority queue’s extractMax operation, applied directly on the input array itself rather than a separate structure. Every time I move the maximum element to the end of the active heap region and shrink the heap, I’m doing exactly what extractMax does in a priority queue — except instead of discarding the extracted maximum or storing it elsewhere, I let it settle into its final sorted position within the very same array I’m heapifying.
This is what makes Heap Sort in-place: the “sorted” region and the “heap” region share the same underlying array, growing and shrinking respectively from the same fixed block of memory, with no extra allocation needed beyond the array I started with.
Mathematical Foundation
Heap Sort’s total running time is the sum of two phases.
Phase 1 — Build-max-heap: Although a naive analysis might suggest $O(n \log n)$ (since I call heapify, which is $O(\log n)$, on $n/2$ non-leaf nodes), a tighter analysis shows this phase actually runs in:
$$ T_{\text{build}}(n) = O(n) $$
This is because most nodes in a heap are near the bottom, where heapify does very little work, and only a few nodes near the top require work proportional to $\log n$. I derive this bound rigorously in my companion article on building a heap, using the sum:
$$ \sum_{h=0}^{\lfloor \log n \rfloor} \left\lceil \frac{n}{2^{h+1}} \right\rceil O(h) = O(n) $$
Phase 2 — Repeated extraction: I perform $n – 1$ extractions, and each one involves a swap ($O(1)$) followed by a heapify call, which costs $O(\log n)$ in the worst case (bounded by the height of the heap). So this phase costs:
$$ T_{\text{extract}}(n) = \sum_{i=1}^{n-1} O(\log i) = O(n \log n) $$
Total running time:
$$ T(n) = T_{\text{build}}(n) + T_{\text{extract}}(n) = O(n) + O(n \log n) = O(n \log n) $$
The $O(n \log n)$ extraction phase dominates the $O(n)$ build phase, so the overall asymptotic complexity of Heap Sort is:
$$ T(n) = O(n \log n) $$
Diagrams
Here’s the two-phase structure of Heap Sort at a high level:
flowchart TD
A[Unsorted Array] --> B["Phase 1: Build Max-Heap (O(n))"]
B --> C["Phase 2: Repeated Extraction (O(n log n))"]
C --> D[Swap root with last element in heap region]
D --> E[Shrink heap size by 1]
E --> F[Heapify at root to restore heap property]
F --> G{Heap size > 1?}
G -- Yes --> D
G -- No --> H[Array is Fully Sorted]And here’s a diagram showing how the array is conceptually divided during the extraction phase:
flowchart LR
A["Array of size n"] --> B["Heap region: indices 0 to heapSize-1"]
A --> C["Sorted region: indices heapSize to n-1"]
B --> D["Shrinks by 1 each extraction"]
C --> E["Grows by 1 each extraction, holds final sorted values"]Pseudocode
HEAP-SORT(A, n)
BUILD-MAX-HEAP(A, n)
for i = n - 1 down to 1
swap A[0] and A[i]
heapSize = i // shrink the active heap region
HEAPIFY(A, heapSize, 0)
HEAPIFY(A, heapSize, i)
largest = i
left = 2*i + 1
right = 2*i + 2
if left < heapSize and A[left] > A[largest]
largest = left
if right < heapSize and A[right] > A[largest]
largest = right
if largest != i
swap A[i] and A[largest]
HEAPIFY(A, heapSize, largest)
BUILD-MAX-HEAP(A, n)
for i = floor(n/2) - 1 down to 0
HEAPIFY(A, n, i)
Step-by-Step Example
Let me trace through the array:
$$ [12, 11, 13, 5, 6, 7] $$
Phase 1 — Build max-heap: After running buildMaxHeap, the array becomes a valid max-heap. Tracing the heapify calls at indices 2, 1, and 0 (as described in my build-heap companion article’s methodology applied to this array), the heap array becomes:
$$ [13, 11, 12, 5, 6, 7] $$
Phase 2 — Repeated extraction:
Iteration $i=5$: Swap root (13) with last element (7) → $[7, 11, 12, 5, 6, 13]$. Heap size shrinks to 5. Heapify at root: 7 vs children 11, 12 → largest is 12 (index 2), swap → $[12, 11, 7, 5, 6, 13]$; 7 (now index 2) has no children within heap size 5, so heapify stops. Array: $[12, 11, 7, 5, 6, 13]$.
Iteration $i=4$: Swap root (12) with element at index 4 (6) → $[6, 11, 7, 5, 12, 13]$. Heap size shrinks to 4. Heapify at root: 6 vs children 11, 7 → largest is 11 (index 1), swap → $[11, 6, 7, 5, 12, 13]$; 6 (now index 1) vs child at index 3 (5) → 6 is already larger, stop. Array: $[11, 6, 7, 5, 12, 13]$.
Iteration $i=3$: Swap root (11) with element at index 3 (5) → $[5, 6, 7, 11, 12, 13]$. Heap size shrinks to 3. Heapify at root: 5 vs children 6, 7 → largest is 7 (index 2), swap → $[7, 6, 5, 11, 12, 13]$.
Iteration $i=2$: Swap root (7) with element at index 2 (5) → $[5, 6, 7, 11, 12, 13]$. Heap size shrinks to 2. Heapify at root: 5 vs child 6 (index 1) → swap → $[6, 5, 7, 11, 12, 13]$.
Iteration $i=1$: Swap root (6) with element at index 1 (5) → $[5, 6, 7, 11, 12, 13]$. Heap size shrinks to 1, loop ends.
Final array:
$$ [5, 6, 7, 11, 12, 13] $$
This matches exactly what my tested C implementation produces.
Time Complexity
- Best Case: $O(n \log n)$ — even if the input happens to already be sorted, Heap Sort still performs the full build and extraction process, since it doesn’t have an early-exit optimization.
- Average Case: $O(n \log n)$ — consistent regardless of input distribution.
- Worst Case: $O(n \log n)$ — Heap Sort has no pathological worst case the way QuickSort does, since the heap height is always $O(\log n)$ regardless of input arrangement.
Space Complexity
Heap Sort requires only:
$$ O(1) $$
auxiliary space (a constant number of temporary variables for swaps), plus $O(\log n)$ stack space if heapify is implemented recursively (as I do in my C implementation). An iterative version of heapify can reduce this to strictly $O(1)$ total auxiliary space.
Correctness Analysis
I verify correctness in two stages.
Build-max-heap correctness: By induction on the order of processing (from the last non-leaf node up to the root), I know that when heapify is called on any node $i$, both of its child subtrees are already valid max-heaps (this is guaranteed since I process nodes in reverse level order, and leaves are trivially valid heaps of size 1). heapify then correctly restores the heap property at node $i$, so the entire tree rooted at $i$ becomes a valid heap. By the time this process reaches the root, the whole array is a valid max-heap.
Extraction phase correctness: At the start of each iteration, I maintain the invariant that A[0..heapSize-1] is a valid max-heap, and A[heapSize..n-1] contains the largest n - heapSize elements in sorted order. Swapping the root (the current maximum of the heap region) with the last heap element, then shrinking the heap size by one, correctly places that maximum into its correct final sorted position, extending the sorted region by one element while removing it from the heap’s responsibility. Calling heapify on the new root restores the heap property for the now-smaller heap region, preserving the invariant for the next iteration.
By induction, once the heap size reaches 1, the entire array (aside from the single remaining heap element, which is by definition the smallest and correctly placed at index 0) is sorted.
Advantages
- Guaranteed $O(n \log n)$ worst-case time complexity, unlike QuickSort’s $O(n^2)$ worst case.
- Sorts in-place with only $O(1)$ auxiliary space (excluding recursion stack), unlike Merge Sort’s $O(n)$ auxiliary array requirement.
- Predictable, consistent performance across best, average, and worst cases.
- Directly reuses the well-understood binary heap structure, which also underlies priority queues.
Disadvantages
- Not stable — equal elements can end up in a different relative order than they started in.
- Poor cache performance in practice compared to QuickSort, since heap operations often jump between distant array indices rather than accessing memory sequentially.
- Generally slower in practice than a well-tuned QuickSort on random data, despite having a better worst-case guarantee.
- Less intuitive to reason about during debugging, since the “sorted” and “heap” regions overlap within a single array rather than being conceptually separate.
Applications
- Situations requiring a strict $O(n \log n)$ worst-case guarantee, such as real-time systems where unpredictable QuickSort worst-case behavior is unacceptable.
- As a fallback within hybrid sorting algorithms like Introsort, which starts with QuickSort but switches to Heap Sort if recursion depth grows too large (indicating a potential worst-case QuickSort scenario).
- Selection algorithms — finding the $k$ largest or smallest elements efficiently, since a partially-built heap can extract the top $k$ elements in $O(n + k \log n)$ time.
- Any embedded or memory-constrained environment where the $O(1)$ auxiliary space requirement is essential.
Implementation in C
Here is my tested, complete implementation:
#include <stdio.h>
// Swaps two integers via pointers
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// Restores the max-heap property at index i, assuming subtrees
// rooted at its children are already valid max-heaps.
void heapify(int arr[], int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
swap(&arr[i], &arr[largest]);
heapify(arr, n, largest); // repair the affected subtree
}
}
// Converts an arbitrary array into a valid max-heap in O(n) time
void buildMaxHeap(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
}
// Full Heap Sort: build a max-heap, then repeatedly extract the max
void heapSort(int arr[], int n) {
buildMaxHeap(arr, n);
for (int i = n - 1; i > 0; i--) {
swap(&arr[0], &arr[i]); // move current max to its sorted position
heapify(arr, i, 0); // restore heap property on the shrunk heap
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Before sorting: ");
printArray(arr, n);
heapSort(arr, n);
printf("After sorting: ");
printArray(arr, n);
return 0;
}
Sample Input and Output
Input:
12 11 13 5 6 7
Output (verified by compiling and running the code above):
Before sorting: 12 11 13 5 6 7
After sorting: 5 6 7 11 12 13
Optimization Techniques
- Iterative heapify: Replacing the recursive
heapifyfunction with an iterative loop removes the $O(\log n)$ recursion stack overhead, achieving strictly $O(1)$ auxiliary space. - Bottom-up heapsort variant: A well-known optimization reduces the number of comparisons during extraction by first finding the path of larger children down to a leaf, then inserting the displaced element via a binary search on that path, reducing comparisons in the extraction phase from roughly $2\log n$ to $\log n$.
- Cache-conscious layouts: Some implementations reorder or pad the array to improve cache locality, since heap operations access non-contiguous indices ($2i+1$, $2i+2$) that don’t naturally benefit from sequential prefetching.
- Ternary (d-ary) heaps: Using more children per node reduces heap height, which can reduce the number of levels traversed during heapify, at the cost of more comparisons per level.
Common Mistakes
- Using the wrong heap size during extraction. A common bug is calling
heapifywith the full array sizeninstead of the shrinkingheapSize(oriin my implementation), which lets the heap incorrectly “see” already-sorted elements as if they were still part of the heap. - Forgetting that
buildMaxHeaponly needs to start fromn/2 - 1. Starting from index 0 or processing all nodes redundantly (including leaves) wastes time, since leaves are trivially valid heaps needing no repair. - Confusing Heap Sort with a priority queue. While both use heaps, Heap Sort repurposes a single array for both the heap and the sorted output, whereas a priority queue is a standalone structure meant to be used repeatedly, not just once to produce a static sorted array.
- Assuming Heap Sort is stable, and using it in a context requiring stability without an appropriate workaround (like attaching original indices as tie-breakers).
- Off-by-one errors in child index calculations, especially confusing 0-indexed formulas ($2i+1$, $2i+2$) with 1-indexed formulas ($2i$, $2i+1$) when adapting pseudocode from different textbook conventions.
Further Reading
- Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (CLRS), MIT Press — https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
- J.W.J. Williams, “Algorithm 232 – Heapsort”, Communications of the ACM, 1964 — https://dl.acm.org/doi/10.1145/512274.512284
- R.W. Floyd, “Algorithm 245: Treesort 3”, Communications of the ACM, 1964 — https://dl.acm.org/doi/10.1145/355588.365103
- Wikipedia, “Heapsort” — https://en.wikipedia.org/wiki/Heapsort
- Visualgo, Sorting Visualization — https://visualgo.net/en/sorting
