Question

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?

Answer 1

Answer:

Both of them are Θ(nlgn).

Explanation:

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 lgk operations. Since:

∑i=1n−1lgk=lg((n−1)!)=Θ(nlgn)

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 Θ(nlgn).