What is the runtime of HEAPSORT on an array A of length n that is already sorted in increasing order? What about decreasing order? Explain your answer in sufficient details.

HEAP-SORT(A) // Input: A: an (unsorted) array // Output: A modified to be sorted from smallest to largest // Running Time: O(n log n) where n = length[A] 1 BUILD-MAX-HEAP(A) 2 for i = length[A] downto 2 3 exchange A[1] and Ald 4 heap-size[A] - heap-size[A] - 1 5 MAX-HEAPIFY(A, 1) MAX-HEAPIFY(A, 4) // Input: A: an array where the left and right children of i root heaps (but i may not), i: an array index // Output: A modified so that i roots a heap // Running Time: O(logne) where n = heap-size[A] i 11+ LEFT(0) 2 + RIGHT(1) 3 if I A[i] largest +1 5 else largesti 7 6 if r