Heapsort Time Complexity Analysis
You'll learn: Why heapsort consistently delivers O(n log n) performance in all cases, even the worst-case scenario.
Understanding the Two Phases
Heapsort consists of two distinct phases, and analyzing each reveals where the time complexity comes from.
Phase 1: Building the Max Heap
You've already learned that building a heap from an unsorted array takes O(n) time using the bottom-up construction method. This is a one-time cost at the beginning of the algorithm.
Phase 2: The Sorting Phase
After building the heap, you perform n extract-max operations. Each extract-max:
- Removes the root (the maximum element)
- Moves it to the end of the array
- Calls heapify-down to restore the heap property
Since each heapify-down operation takes O(log n) time (bubbling down through the height of the heap), and you do this n times, Phase 2 costs O(n log n).
Why O(n log n) in All Cases
Combining both phases: O(n) + O(n log n) = O(n log n) overall.
What makes heapsort special is that this holds for best-case, average-case, and worst-case scenarios. Unlike quicksort (which can degrade to O(n²)), heapsort's performance doesn't depend on the input order. Whether the array is sorted, reverse-sorted, or random, you still build one heap and extract n elements.
Think of it like a factory assembly line: no matter what raw materials arrive, the process takes the same number of steps.
Key Takeaway:
Heapsort achieves O(n log n) worst-case time complexity because it builds a heap in O(n) time and performs n extract-max operations, each costing O(log n), giving guaranteed performance regardless of input.