Visualize Heap Sort step by step. See how the array is first transformed into a max-heap via heapify, then elements are extracted one by one to produce a sorted sequence.
Heap Sort uses a max-heap data structure to find the largest element efficiently, then repeatedly extracts it to build a sorted array.
Transform the array into a max-heap where every parent node is greater than its children.
Swap the root element (the largest) with the last element in the heap. Now the last position is sorted.
Reduce the heap size by 1 and restore the max-heap property (heapify) so the new root is the next largest.
Keep extracting the max and heapifying until all elements are in sorted order.
Heap Sort is an in-place, O(N log N) algorithm. It is not stable, and cache performance is generally worse than Quick Sort.