HEAPSORT( array A, int n)

1 BUILD-HEAP(A, n)
2 m n
3 while (m  2)
4 do SWAP(A[1],A[m])
5 m m- 1
6 HEAPIFY(A, 1,m)

Let the pseudo code of Heap Sort reply following questions (you need to justify your answers as well),

a. Determine the running time of Heap Sort if input is sorted in ascending order

b. Determine the running time of Heap Sort if input is sorted in descending order

c. What is best case input (format of input resulting in best case time) for Heap Sort.