The number of comparisons performed during an ordinary heapsort is of
order . Thus the cost to sort each page internally is .
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 . 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.

Sat Apr 3 18:07:59 METDST 1999