The external heapsort as described can only handle completely full pages. Since any general purpose sort must be able to sort an arbitrary number of elements, this is not an acceptable limitation. Fortunately there is a simple solution which does not compromise the performance of the sort.

The solution is to define that the incomplete page needed, is always
the last page of the heap.- Then, instead of swapping the top node
with the last node, it is swapped with the *S* last elements, taken
from the two last nodes. This ensures that the new top element is
completely refilled.

The extra cost is 1 page access for every *S* elements, for a total of
*M* page accesses, and the internal cost of merging the elements from
the two last pages, for a total of *N*/2 comparisons.

Sat Apr 3 18:07:59 METDST 1999