next up previous contents
Next: Performance tuning. Improving the Up: Implementing the external heapsort Previous: Implementing the external heapsort

Making the external heapsort practical.

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.

Jesper Bojesen
Sat Apr 3 18:07:59 METDST 1999