Heap Sort

How It Works

Heap sort keeps the largest value at the root of a max heap. First it heapifies the array bottom-up, then it swaps the root into the sorted suffix and restores heap order on the remaining prefix.

• Yellow marks comparisons between parent and child candidates.
• Red marks an actual swap in both the array and the heap tree.
• Green marks indices that have left the heap and reached final sorted positions.