HEAPSORT$($A$)$

$1$ BUILD$-$MAX$-$HEAP$($A$)$

$2$ for i $=$ A$.$length downto $2$

$3$ exchange A$[1]$ with A$[$i$]$

$4$ A$.$heapsize $=$ A$.$heapsize $1$

$5$ MAX$-$HEAPIFY$($A$,1)$

$(10$ points$)$ Argue the correctness of HEAPSORT using the following loop invariant:

At the start of each iteration of the for loop of lines $2-5,$ the subarray A$[1..$ i$]$ is a

max$-$heap containing the i smallest elements of A$[1..$ n$],$ and the subarray A$[$i $+1..$ n$]$

contains the n $$ i largest elements of A$[1..$ n$],$ sorted.

Make sure that your loop invariant fulfills the three necessary properties.

Problem $2-2.(10$ points$)$ 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?

Problem $2-3.(5$ points$)$ Show that the worst$-$case running time of HEAPSORT is $\backslash$Omega $($n lg n$).$

Problem $2-4.(5$ points$)$ Show that the running time of QUICKSORT is $\backslash$Theta $($n

$2$

$)$ when the array A

contains distinct elements and is sorted in decreasing order.