$1.$Using the following code as a model, illustrate the operation of INSERTION$-$SORT on

the array $A=(31,41,59,26,41,58)$

INSERTION$-$SORT $(A,n)$

for $j=2ton$

key$=A[j]\frac{?}{\frac{?}{?}}$

Insert $A[j]$ into the sorted sequence $A[1$dotsj$-1]$

$i=j-1$

while $i>0$ and $A[i]>$ key

$A[i+1]=A[i]$

$i=i-1$

$A[i+1]=$ key

$2.$Rewrite the INSERTION$-$SORT procedure to sort into nonincreasing instead of non$-$

decreasing order.

$3.$Illustrate the operation of insertion sort on the array