Key points are not available for this paper at this time.
Abstract This paper completes analysis of the worst-case running time of Heapsort measured by the number of comparisons of keys performed while sorting. A derivation of an exact formula for the maximum number of comparisons of keys performed by Heapsort on any array of size N 2 is presented. It is equal to align N 2 ^ N - 4 \\4pt 0 otherwise. array. align The above formula allows for deciding, in O (N N) time, if any given N -element array is a worst-case array for Heapsort. Its proof yields an algorithm for construction, in O (N N) time, of worst-case arrays of arbitrary sizes N 2 for Heapsort.
Marek A. Suchenek (Wed,) studied this question.