next up previous contents
Next: Implementing the external heapsort Up: The External Heapsort Previous: The external siftdown procedure

The internal cost of external heaps

  The number of comparisons performed during an ordinary heapsort is of order tex2html_wrap_inline1383 . Thus the cost to sort each page internally is tex2html_wrap_inline1385 . Also it is quite clear that the number of merges performed during an external sort must follow this same performance model. I.e. The number of merges is of order tex2html_wrap_inline1387 . Since we do M internal sorts and since each merge takes at most S comparisons, we arrive at this number of comparisons for the complete external heapsort:


This result is important. It means that the expected number of comparisons does not depend on the page size!. Thus we have the freedom to optimize the page size with respect to the memory subsystem available, without having to worry about the internal cost. Also it means that we do not need to consider the dubious alignment of the heap in memory used by the d-heaps to keep the fanout down. The wasted work at the end of a physical page can be amortized away by selecting the logical page size sufficiently larger than the physical page size, so that the cost of loading the last physical page of a logical page is neglectable.

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