The Best Case of Heapsort

Abstract:

Heapsort is a fundamental algorithm whose precise performance characteristics are little understood. It is easy to show that the number of keys moved during the algorithm is N lgN +O(N) in the worst case, and it is conjectured that the average case performance is the same, though that seems very difficult to
prove. In this paper, we show by construction that the best case for the number of moves is approximately 1/2N lgN. This destroys the conjecture that Heapsort is asymptotically flat (a possible easy road to the average-case asymptotic analysis), and also implies that a variant of Heapsort suggested by Floyd is not asymptotically optimal in the worst case. The construction was suggested by results of an empirical study that involved generating and analyzing hundreds of billions of heaps. Other facts learned from this study about the distribution of the number of moves required by Heapsort are presented.