Using heaplab, a plot of the running time for the standard heapsort described in chapter 2 on two different machines was produced with an element size of 8 bytes. The result is in figure 5.1.
Figure 5.1: Standard Heapsort on PowerPC 332MHz and P2SC 160MHz
It is immediately observed that the performance of heapsort does not follow the theory very well. Especially on the faster machine the curve is far from the straight line it should be if the running time truly was O(NlogN). This is of course due to an increased cache miss rate when the problem size grows.
The cache size of the P2SC is 16K elements while the PPC has a first level cache of 4K elements and a second level cache of 32K elements. These numbers fits nicely with the points where the curves breaks.