Worst-Case Analysis of Heapsort, Exactly

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& 2(N-1) N - 2 N +1 - 2 s₂(N) - e₂(N) + min ( N , 3) + 5 + c, align where s₂(N) is the sum of digits of the binary representation of N, e₂(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 align& c = \ array@ll 1 if \; N ≤ 2 N - 4 \\[4pt] 0 otherwise. array . 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 Heapsort. Its proof yields an algorithm for construction, in O(N log N) time, of worst-case arrays of arbitrary sizes N ≥ 2 for Heapsort.