209. Explain heap sort and its properties.
MediumPriority queues & heaps
Technical
Show model answer
Build a max-heap in place bottom-up (O(n)). Then repeatedly swap the root (current maximum) with the last element of the heap region, shrink the region by one and sift the new root down. After n − 1 steps the array is sorted ascending.
Time is O(n log n) in the best, average and worst case, with O(1) extra space. It is not stable and has poor cache locality compared with quicksort, which is why introsort uses it only as a fallback to guarantee O(n log n) when quicksort recursion gets too deep.