ON THE BEST CASE OF HEAPSORT

Although discovered some 30 years ago, the Heapsort algorithm is still not completely understood. Here we investigate the best case of Heaps ort. Contrary to claims made by some authors that its time complexity is O(n), i.e., linear in the number of items, we prove that it is actu ally O(n log n) and is, in fact, approximately half that of the worst case. Our proof contains a construction for an asymptotically best-cas e heap. In addition, the proof and construction provide the warst-case time complexity and an asymptotically worst-case example for Bottom-u p versions of Heapsort. (C) 1996 Academic Press, Inc.