25. How does heap sort work?
MediumPriority queues & heaps
Technical
Show model answer
Build a max-heap from the array in O(n), then repeatedly swap the root (the maximum) with the last element of the heap, shrink the heap by one and sift the new root down. Total O(n log n), in place, but not stable and less cache-friendly than quicksort.