Skip to interview prep
Apexed

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.

How does heap sort work — Data structures & algorithms interview question — Apexed