$($a$)$ State the loop invariant $\backslash ($ P$($k$)\backslash )$ for the $\backslash ($ k $\backslash )-$th iteration of insertion sort.

$($b$)$ Use insertion sort to sort the following list of numbers. Show the state of the list after each iteration of the outer for$-$loop of insertion sort. For each iteration $\backslash ($ k $\backslash ),$ circle the first $\backslash ($ k $\backslash )$ elements of the partially$-$sorted list. According to the loop invariant of insertion sort, these should be appear in sorted order.

$\backslash [$

$[2,1,8,3,5,6,7,4]$

$\backslash ]$