2. [25points] Sort the array A - <27, 18, 4, 5, 22, 95, 35, 11, 17> using the Heapsort algorithm

as given in the textbook (CLRS).

(a) Show the array after the BUILD-MAX-HEAP is returned.

(b) How many comparisons are made by the BUILD-MAX-HEAP?

(c) How many comparisons are made in total after the array is sorted?

(d) Is an array in increasing order a best case, worst case, or a case in between for the

Heapsort? Justify your answer.

(e) Use a simple example to show Heapsort is not stable.