The Analysis of Heapsort

Abstract:

Heapsort is a fundamental algorithm whose precise performance characteristics have proven difficult to analyze. It is easy to show that the number of keys moved during the algorithm when sorting a random file of N distinct elements is N log N + O(N) in the worst case, and it has long been conjectured that the average case performance is the same. No specific results on the average case or even the best case have been found despite the algorithm's standing as a classic method that is in widespread use. In this paper, we resolve these questions by showing that the best case for the number of moves is ~ 1/2N log N and that the average number of moves is ~ N log N.
These results have implications for the analysis of various modified versions of the algorithm that have been suggested. In particular, they imply that a well-known variant originally due to Floyd uses an asymptotically optimal number of comparisons on average, but three-halves that in the worst case.
This essentially completes the analysis of the algorithm, though there is another quantity that contributes to the leading term of the running time that requires more intricate arguments, and we have little specific information about the distribution beyond what is implied by our asymptotic results.
REVISED January 1992.