Heap sort
Scenario
You need a sorting algorithm that is guaranteed to run in `O(n log n)` time no matter what malicious input you get, and it must use `O(1)` extra memory.
Merge sort uses `O(n)` memory, and Quicksort can degrade to `O(n^2)`. Is there a sort that guarantees both `O(n log n)` time and `O(1)` space?
Why it exists
Problem: Quicksort is fast in practice but has an `O(n^2)` worst-case. Merge sort guarantees `O(n log n)` but requires `O(n)` auxiliary space.
Naive approach: Use quicksort and hope no adversary provides a worst-case input array, or use merge sort and pay the memory cost.
Better idea: Build a max-heap in the array (`O(n)`), then repeatedly swap the root (the maximum) with the last element of the unsorted portion and shrink the heap. This sorts the array in-place with a strict `O(n log n)` worst-case time guarantee.
Mental model
Turn the array into a max-heap, then keep tearing off the root (the largest item) and placing it at the end of the array, rebuilding the heap with the remaining items.
Heap sort has two phases. First, it builds a max-heap from the array in `O(n)` time using the backward sift-down method.
Second, it repeatedly swaps the root of the max-heap (which is the current maximum) with the end of the heap boundary, shrinking the boundary by one. The newly swapped root is then sifted down to restore the max-heap property. When the heap empties, the array is sorted in ascending order.
Repeated decision: Swap the root to the front of the sorted tail, shrink, then sift the new root down — which child does it swap with (the larger one)?
Explanation
Heap sort cleverly repurposes the array into two logical sections: the unsorted prefix (which maintains a valid max-heap) and the sorted suffix.
1. **Build the Heap**: Convert the entire array into a max-heap in `O(n)` time. The largest element is now sitting at index `0`.
2. **Extract and Sort**: Swap the element at index `0` with the last element in the heap. Now, the absolute largest element is at the end of the array — exactly where it belongs in a sorted list. Logically reduce the size of the heap by `1` (the sorted suffix grows by `1`).
3. **Sift Down**: The element we just swapped to the root is likely small and violates the heap property. Sift it down the tree by swapping it with its larger child until it settles.
4. **Repeat**: Continue swapping the root to the end of the heap and sifting down. After `n` extractions, the array is fully sorted in ascending order.
The algorithm trades speed for guarantees, offering strictly in-place `O(1)` space and `O(n log n)` worst-case time. However, it exhibits poor cache locality because the sift-down jumps erratically across the array. It is also an unstable sort because swapping the root with the last leaf launches elements across the array.
Key points
- `O(n)` Build, `O(n log n)` Sort: Building the initial heap takes `O(n)` time. Extracting the root `n` times takes `O(n log n)`.
- Strictly `O(1)` Space: The entire process happens in-place by manipulating indices, requiring no extra scratch array.
- Unstable and Cache-unfriendly: Heap sort does not preserve the order of equal elements, and its jumping access pattern makes it slower than quicksort in practice.
Pattern: Heap Sort
Recognition cues:
- Requirements demand `O(1)` extra space and guaranteed `O(n log n)` time.
- Embedded systems or memory-constrained environments needing a robust sort.
Engineering examples
Introsort (`std::sort`)
Standard libraries need a fast sort (like quicksort) but cannot risk a malicious user providing input that triggers `O(n^2)` behavior.
Introsort uses quicksort initially but monitors the recursion depth. If it detects pathological `O(n^2)` behavior, it instantly switches to heap sort to guarantee an `O(n log n)` finish.
Embedded Systems
Sorting on microcontrollers with highly constrained RAM where allocating an `O(n)` buffer for merge sort is impossible.
Heap sort's strict `O(1)` space overhead ensures the device won't run out of memory.
When not to use
- General purpose sorting in high-level applications: Quicksort is almost always faster in practice due to sequential memory access (better cache locality). Merge sort or Timsort is preferred when stability is required.
Common mistakes
- Thinking heap sort is stable: Heap sort is inherently unstable. Swapping the root with the last leaf launches elements across the array, destroying the relative order of duplicate keys.
- Confusing sort direction: To sort an array in ASCENDING order, you must use a MAX-heap. The max elements are repeatedly swapped to the END of the array.
- Thinking it is always faster than quicksort: Despite a better worst-case time, heap sort has worse constant factors and terrible CPU cache behavior. Quicksort usually wins in reality.
- Thinking building the heap takes `O(n log n)`: Floyd's bottom-up heap construction runs in strict `O(n)` time. The `O(n log n)` cost comes entirely from the extraction phase.
Glossary
- in-place
- An algorithm that modifies the original array without needing extra memory proportional to the input size.
- stable
- A sorting algorithm that preserves the original relative order of equal elements. Heap sort is NOT stable.
- introsort
- A hybrid sorting algorithm used in standard libraries that starts with quicksort but switches to heap sort if the recursion goes too deep.
Recall questions
- Why does heap sort use a max-heap to sort in ascending order?
- What is the worst-case time complexity and space complexity of heap sort?
- What happens after the root is swapped with the last element of the heap?
Questions & answers
Why is quicksort generally preferred over heap sort despite quicksort having an `O(n^2)` worst case?
Quicksort has much better cache locality. Its pointers scan sequentially, which modern CPU caches predict perfectly. Heap sort's sift-down operations jump wildly across memory indices, causing frequent cache misses.
Approach: Highlight hardware realities (cache locality) versus pure algorithmic Big-O.
Is heap sort a stable sorting algorithm? Why or why not?
No. When the maximum element is swapped with a leaf node across the array, it frequently jumps over duplicate values, destroying their original relative order.
Approach: Explain the long-distance swap mechanism.
Continue learning
Previous: Binary heap
Related: Merge Sort
Related: Binary heap