Recall the Insertion$-$Sort algorithm

InSERTION$-$Sort $(A,n)$

for $j=2$ to $n$

key $=A[j]$

$i=j-1$

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

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

$,i=i-1$

$A[i+1]=$ key

You have seen a correctness proof of the algorithm based on the following loop invariant for the $($outer$)$ for loop:

Let $A_j[1,$dots,$n]$ denote the array at the beginning of iteration $j($end of iteration $j-1).$ We have that $A_j[1,$dots,$j-1]$ stores the same values as $A[1,$dots,$j-1]$ but in sorted order, while $A_j[l]=A[l]$ for $jln.$

In this problem, you will fill in a bit more detail in the proof, by also introducing a loop invariant for the $($inner$)$ while loop. You will use the following loop invariant:

Let $A_{j,i}[1,$dots,$n]$ denote the array at the beginning of iteration $i$ of the inner loop $($for $0ij-1).$ Then:

If the loop executes with value $i+1,$ then

$A_{j,i}[1,$dots,$i]=A_j[1,$dots,$i],$ and

If $i+2j,$ then $A_{j,i}[i+2,$dots,$j]=A_j[i+1,$dots,$j-1]$ and