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?

The initial ordering of the input array does not change the overall runtime of HEAPSORT. The call to BUILD-MAX-HEAP still takes \(\Theta(n)\) time as the initial order only impacts this runtime by a constant factor which is ignored.

At this point the two cases converge since our array is now a max heap in both cases. The inner lines of the for loop may end up traversing the entire height of the heap and thus take \(\Theta(\lg n)\) time. Because of the loop itself, we are performing these steps \(n\) times and so the total run time (in both cases) is \(\Theta(n \lg n) + \Theta(n) = \Theta(n \lg n)\).