What is the running time of heapsort on an array A of length n that is already sorted in ascending order? How about the descending order?
Hence the running time of heapsort will be \( O(nlogn) \) for n elements in the array. |