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})$.