Argue the correctness of HEAPSORT using the following loop invariant:

At the start of each iteration of the for loop of lines $235,$ the subarray A$1$ W i$$

is a max$-$heap containing the i smallest elements of A$1$ W n$,$ and the subarray A$$i C $1$ W n$$ contains the n $$ i largest elements of A$1$ W n$,$ sorted.