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