🔺 Heapsort

How It Works

1. Build Max-Heap: Convert array to max-heap (O(n))
2. Extract Max: Swap root with last element, reduce heap size
3. Heapify: Restore heap property by sifting down
4. Repeat until heap is empty

Complexity

• Time: O(n log n) — always
• Space: O(1) — in-place
• Not Stable