Worst-Case Analysis of Heapsort, Exactly.

This paper completes analysis of the worst-case running time of |$ {\tt{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 |$ {\tt{Heapsort}} $| on any array of size |$ N \geq 2 $| is presented. It is equal to $$ \begin{align}& \nonumber 2(N-1)\lceil \lg N \rceil - 2 ^{\lceil \lg N \rceil +1} - 2 s_2(N) - e_2(N) + \min (\lceil \lg N \rceil, 3) + 5 + c, \end{align} $$ where |$s_2(N)$| is the sum of digits of the binary representation of |$N$|⁠ , |$e_2(N)$| is the exponent of |$2$| in the |$N$| 's prime factorization and |$ c $| is a binary function on the set of positive integers defined by $$ \begin{align}& \nonumber c = \left\{ \begin{array}{@{}ll} 1 \text{ if} \; N \leq 2 ^{\lceil \lg N \rceil} - 4 \\[4pt] 0 \text{ otherwise}. \end{array} \right. \end{align} $$ The above formula allows for deciding, in |$ O(N \log N) $| time, if any given |$ N $| -element array is a worst-case array for |$ {\tt{Heapsort}} $|⁠. Its proof yields an algorithm for construction, in |$ O(N \log N) $| time, of worst-case arrays of arbitrary sizes |$ N \geq 2 $| for |$ {\tt{Heapsort}} $|⁠. [ABSTRACT FROM AUTHOR]