= Heapsort
{title2=$T_{\max}(n)=O(n\log n)$}
{wiki}
Build a <max-heap> in an <array>, then repeatedly exchange its root with the last element of the active heap and restore <heap order> by <heapify down>. The inactive suffix grows in ascending order. Bottom-up heap construction costs $O(n)$ because the number of nodes at height $h$ decreases geometrically, and the extraction phase costs $O(n\log n)$. Iterative sifting uses constant auxiliary storage. Long-distance exchanges can reverse equal-key records, so the usual version does not provide <stable sorting>.
Back to article page
