Heap Sort

Build a max-heap, then extract max repeatedly. LC 215, 347, 973.

Heap
Sifting
Swapping
Sorted

Controls

Time: O(n log n) always | Space: O(1) | Not stable

Steps