Once the max heap has been built, heapsort proceeds to the selection sorting phase. In this phase the sorted sequence is obtained by repeatedly withdrawing the largest element from the max heap. Figure illustrates how this is done.

The largest element of the heap is always found at the root
and the root of a complete tree is always in array position one.
Suppose the heap occupies array positions 1 through *k*.
When an element is withdrawn from the heap,
its length decreases by one.
I.e., after the withdrawal the heap occupies array positions 1 through *k*-1.
Thus, array position *k* is no longer required by the max heap.
However, the next element of the sorted sequence belongs in position *k*!

So, the sorting phase of heapsort works like this:
We repeatedly swap the largest element in the heap (always in position 1)
into the next position of the sorted sequence.
After each such swap,
there is a new value at the root of the heap and
this new value is pushed down into the correct position in the heap
using the `PercolateDown` routine.

Program gives the `DoSort` routine
of the `HeapSorter<T>` class.
The `DoSort` routine embodies both phases of the heapsort algorithm.
However, before it starts the first phase of the algorithm,
`DoSort` sets the array base to one.
This modification of the array base simplifies the coding of the algorithms.
As discussed in Section
the array base will have been set to zero by the
`Sort` member function of the `Sorter<T>` base class
and will be restored to the original base by that routine.

**Program:** `HeapSorter<T>` Class `DoSort` Member Function Definition

In the first phase of heapsort
the `BuildHeap` routine is called to transform
the array into a max heap.
As discussed above, this is done in *O*(*n*) time.

The second phase of the heapsort algorithm builds the sorted list.
In all *n*-1 iterations of the loop on lines 6-10 are required.
Each iteration involves one swap
followed by a `PercolateDown` operation.
Since the worst-case running time for `PercolateDown` is ,
the total running time of the loop is .
The running time of the second phase asymptotically dominates
that of the first phase.
As a result, the worst-case running time of heapsort is .

Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.