Heap Sort - Complexity & Analysis

Complexity Analysis

Heap sort has consistent, predictable performance.

Time Complexity

All Cases: O(n log n)

• Build heap: O(n) - linear time
• Extract n elements: O(n log n) - each extraction is O(log n)
• Total: O(n log n)

Space Complexity

O(1) - Constant Space

• Sorts in-place
• Only uses a few variables
• No extra arrays needed

Why O(n log n)?

• Build heap: O(n) - bottom-up heapify is efficient
• Extract n times: n × O(log n) = O(n log n)
• Total: O(n) + O(n log n) = O(n log n)

Comparison with Other Algorithms

When to Use

Heap sort is ideal when:

• You need guaranteed O(n log n) performance
• Memory is limited (in-place)
• You want to avoid worst-case scenarios
• Building priority queues

Advantages

1. Guaranteed performance: Always O(n log n)
2. In-place: Only O(1) extra space
3. No worst case: Consistent performance
4. No recursion: Can be iterative

Disadvantages

1. Not stable: May change relative order
2. Slower constants: More operations than quicksort
3. Complex: More complex than simple sorts
4. Cache performance: Not as cache-friendly as quicksort

What’s Next?

Let’s test your understanding with practice problems and a quiz.