Heap Sort

J.W.J. Williams, 1964

Heap Sort was introduced by J.W.J. Williams in 1964. It works in two phases: first, it builds a max-heap by sifting down from the middle of the array to the root; then, it repeatedly swaps the root (the maximum) with the last unsorted element and sifts down to restore the heap property. With guaranteed O(n log n) time and O(1) extra space, it combines the best of merge sort's time bound and insertion sort's space efficiency. The visualization shows sift-down comparisons in gold, swapped elements in coral, and the growing sorted tail in teal.