What is Heap Sort? How does it work?

Difficulty: 5/10

heap construction, in-place sorting, time complexity

Heap Sort

Heap Sort builds a max-heap for ascending order, then repeatedly moves the maximum element to the end and restores the heap property over the remaining prefix. It guarantees O(n log n) time and can be performed in-place.

javascript

1
Build heap: O(n).
2
Each extraction: O(log n).
3
Total: O(n log n).
4
Auxiliary space: O(1) for an iterative in-place implementation.
5
Standard Heap Sort is not stable.

Scenario Questions

0-2 years experience

2-5 years experience

1Your team added a new feature that sorts user‑generated lists using heap sort, but you notice performance degrades when the list size exceeds 10,000. Walk me through how you would profile and possibly optimize the implementation.

Follow-up Questions