Consider the implementation below for Insertion Sort, which sorts an array into descending order. public void InsertionSort(int[] array, int n) // PRE: n is the length of the array POST: array is sorted int i; int j; int key: for (j 1; j n; j++) { //Notice starting with 1, not ? // Invariant for the outer Loop: array[0..j-1] is sorted, descending order keyarrayj]: for (1-j - 1; (1 >-?) && (array[1] key) ; i-) { // Move smaller values up one position array[i1] -array[i] array[? + 1] key; // Insert key into proper position (++) return a) Trace the algorithm for the array A 12, 1, 5, 0, 6), and n 5; make sure you keep track of the array after each inner and outer iteration. In your trace, draw a rectangle around the array after each complete iteration of the OUTER loop b) Verify that the array portion A[0..j-1] is sorted after each complete iteration of the outer loop, i.e. underline that portion of the array and check that it is sorted. (Note that A[0.j- 1] means "the portion of the array between, and including, indices 0 and j-1.) Now check the invariant for the outer loop is established (made to be true) by the initialisation of the variable j; i.e. substitute the initial values of the relevant variables into the invariant statement and observer that it is true. c) d) Finally deduce that the postcondition is satisfied after the outer loop has terminated