Exercise 6.4.3

What is the running time of HEAPSORT on an array $A$ of length $n$ that is already sorted in increasing order? What about decreasing order?

Both of them are $\Theta(n\lg{n})$.

If the array is sorted in increasing order, the algorithm will need to convert it to a heep that will take $\O(n)$. Afterwards, however, there are $n-1$ calls to MAX-HEAPIFY and each one will perform the full $\lg{k}$ operations. Since:

$$ \sum_{i=1}^{n-1}\lg{k} = \lg\Big((n-1)!\Big) = \Theta(n\lg{n}) $$

Same goes for decreasing order. BUILD-MAX-HEAP will be faster (by a constant factor), but the computation time will be dominated by the loop in HEAPSORT, which is $\Theta(n\lg{n})$.