Table 8.1 gives simulation results (in actual execution time measured in 1/1000 second intervals). It should be carefully studied. Note that the O(n) and O(n lg n) sorts may be easily identified. The best and worst input cases are also evident, as well as the relatively uniform behavior of heapsort.
Each entry in the table is the average of 20 runs on a VAX 730 under VMS Version 4.0. For each n the five values correspond to input that is sorted, half sorted?/FONT>half random, random, half reverse sorted?/FONT>half random, and reverse sorted. If the entries for heapsort seem counter to your intuition, remember that its implementation sees sorted input as reverse sorted and reverse sorted input as sorted. This is because it uses a min heap to produce descending order.