= Solution
Build a <max-heap>, then repeatedly swap its root with the last element of the active prefix, shrink that prefix and restore <heap order> by <heapify down>. A zero-based implementation is
``
for i = floor(n/2)-1,...,0:
siftDown(A,i,n)
for end = n-1,...,1:
swap A[0],A[end]
siftDown(A,0,end)
``
`siftDown(A,i,end)` repeatedly exchanges entry `i` with its larger child while the child lies below `end` and has a larger key. The suffix beyond `end` is already sorted and never touched again. For the specified input, key stages of <heapsort> are
|| Stage
|| Active max heap
|| Sorted suffix
| Bottom-up heap construction
| $[5,4,3,1,2]$
| $[]$
| Extract 5, repair
| $[4,2,3,1]$
| $[5]$
| Extract 4, repair
| $[3,2,1]$
| $[4,5]$
| Extract 3, repair
| $[2,1]$
| $[3,4,5]$
| Extract 2
| $[1]$
| $[2,3,4,5]$
The final array is \b[$[1,2,3,4,5]$]. Bottom-up construction takes $O(n)$ time because there are progressively fewer nodes at each greater subtree height; the extractions give worst-case $O(n\log n)$ time and constant auxiliary storage for iterative sifting.
Back to article page
