What is Heap Sort?
Learn how heap sort builds a max-heap and extracts the max repeatedly to sort in O(n log n) time and O(1) space.
Expected Interview Answer
Heap sort builds a max-heap from the input array, then repeatedly swaps the root (the current maximum) with the last unsorted element and sifts the reduced heap back into shape, giving a guaranteed O(n log n) time, in-place, non-stable sort.
The first phase, heapify, turns the raw array into a valid max-heap in O(n) time by sifting down every non-leaf node from the middle of the array outward to the root. The second phase repeatedly swaps the root with the last element of the still-unsorted region, shrinks that region by one, and sifts the new root down to restore the heap property, which takes O(log n) per extraction across n extractions. Because everything happens inside the original array with index math instead of pointers, heap sort needs only O(1) extra space, unlike merge sort. It is not stable, since equal keys can be reordered during swaps, and its constant factors are usually worse in practice than a well-tuned quicksort despite sharing the same average-case bound.
- Guaranteed O(n log n) time in every case
- O(1) extra space, fully in place
- No worst-case quadratic blow-up unlike quicksort
- Useful when memory is constrained and predictability matters
AI Mentor Explanation
A groundstaff crew first arranges every player photo on a wall into a rough pyramid where each player above is never shorter than the two below them, working from the middle rows outward so the whole wall satisfies the rule in one pass. Then they repeatedly take the tallest photo at the very top, pin it into a "tallest first" row on the side, and move the last remaining pyramid photo up to the top spot before sinking it back down past shorter children until the pyramid rule holds again. This top-swap-and-resink cycle repeats until every photo has left the pyramid in descending height order. No extra wall space is needed because the same pyramid shrinks by one slot each time a photo is removed.
Step-by-Step Explanation
Step 1
Build a max-heap in place
Sift down every non-leaf node from n/2 - 1 down to 0, giving a valid heap in O(n) time.
Step 2
Swap root with last unsorted element
The root holds the current maximum; swap it into the last position of the unsorted region.
Step 3
Sift the new root down
Shrink the heap by one and sift the swapped-in root down to restore the heap property in O(log n).
Step 4
Repeat until sorted
Continue extracting the max n times; the array ends up sorted ascending, entirely in place.
What Interviewer Expects
- Explain the two phases: build-heap then repeated extraction
- State O(n log n) worst-case time and O(1) extra space
- Note heap sort is not stable
- Compare tradeoffs against quicksort and merge sort
Common Mistakes
- Thinking heapify is O(n log n) instead of the tighter O(n) bound
- Forgetting the array must first be converted to a valid heap before extraction
- Assuming heap sort is stable
- Confusing sift-down direction (root moving down) with sift-up (used for insertion)
Best Answer (HR Friendly)
“Heap sort turns the array into a structure where the largest item is always on top, then repeatedly pulls that largest item off and fixes the structure, building the sorted result from the back forward. I would reach for it when I need guaranteed O(n log n) performance without any extra memory, even if it is not the fastest option in practice.”
Code Example
def heap_sort(arr):
n = len(arr)
def sift_down(start, end):
root = start
while True:
child = 2 * root + 1
if child > end:
break
if child + 1 <= end and arr[child] < arr[child + 1]:
child += 1
if arr[root] < arr[child]:
arr[root], arr[child] = arr[child], arr[root]
root = child
else:
break
for start in range(n // 2 - 1, -1, -1):
sift_down(start, n - 1)
for end in range(n - 1, 0, -1):
arr[0], arr[end] = arr[end], arr[0]
sift_down(0, end - 1)
return arrFollow-up Questions
- Why is building the initial heap O(n) rather than O(n log n)?
- How does heap sort compare to quicksort in real-world performance?
- Can you make heap sort stable? What would it cost?
- How would you use a heap to find the k largest elements without sorting everything?
MCQ Practice
1. What is the time complexity of the heapify (build-heap) phase of heap sort?
Sifting down from the middle of the array outward amortizes to O(n) total work, not O(n log n).
2. What extra space does heap sort require beyond the input array?
Heap sort operates entirely in place using index arithmetic, needing only O(1) auxiliary space.
3. Is heap sort a stable sorting algorithm?
The swaps performed during extraction and sift-down can change the relative order of equal keys, so heap sort is not stable.
Flash Cards
What are the two phases of heap sort? — Build a max-heap in O(n), then repeatedly extract the root and sift down in O(log n) each.
What is heap sort’s worst-case time complexity? — O(n log n), guaranteed in every case.
How much extra memory does heap sort use? — O(1) — it sorts entirely in place within the original array.
Is heap sort stable? — No, equal elements can be reordered by the swaps during extraction.