Given the following code: LEFT(i) return 2i RIGHT(i) return 2i + 1 MaxHeapify(A, i) l = LEFT(i); r = RIGHT(i); if l A[i] largest =

Given the following code:

LEFT(i)

return 2i

RIGHT(i)

return 2i + 1

MaxHeapify(A, i)

l = LEFT(i);

r = RIGHT(i);

if l <= A.heap-size and A[l] > A[i]

largest = l;

else

largest = i;

if l <= A.heap-size and A[r] > A[largest]

largest = r;

if largest != i

exchange A[i] with A[largest]

MaxHeapify(A, largest);

BuildMaxHeap(A)

A.heap-size = A.length

for i = floor(A.length/2) downto 1

MaxHeapify(A, i)

1. 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?

2. What is the worst case running time of heapsort?