Builds a max-heap, then repeatedly swaps the largest element to the end and sifts the root down. In-place, O(n log n).
Builds a max-heap, then repeatedly swaps the largest element to the end and sifts the root down. In-place, O(n log n).
Time complexity: O(n log n). Space complexity: O(1).
Core idea — First rearrange the array into a max-heap (every parent ≥ its children), then repeatedly pull out the largest element.
What each pass accomplishes — Once the heap is built, each iteration swaps the root (the current maximum) to the end of the heap, shrinks the heap by one, and sifts the new root down to restore the heap. So the array fills with the largest values from the back forward.
Use the interactive visualizer above to run Heap Sort on your own input and watch every comparison, swap, and operation animate step by step — pause, scrub, or replay at any speed.