What is the time complexity of Heapsort?

What is the time complexity of Heapsort?

Approach: Analyze building a heap and then repeatedly extracting the max.

O(n log n) in all cases. Building the heap takes O(n), and extracting n elements takes O(n log n).

Follow-up: Is Heapsort stable?

Key concepts: O(n log n), in-place, unstable.