The Sorting Phase

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.

  
Figure: Heap Sorting

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.