Consider the following recursive version of InsertionSort:

procedure InsertionSort(A, n)

**Sorts array A of size n

if n > 1 then

InsertionSort(A, n 1)

x A[n]

PutInPlace(A, n 1, x)

end if

procedure PutInPlace(A, j, x)

if (j = 0) then

A[1] x

else if x > A[j] then

A[j + 1] x

else i.e., x A[j]

A[j + 1] A[j]

PutInPlace(A, j 1, x)

end if

a) First, prove (using induction) the correctness of PutInPlace by showing that:

For any array A, and natural number j such that (i) A has (at least) j + 1 cells, and (ii) the subarray A[1...j] is sorted, when PutInPlace(A, j, x) terminates, the first j + 1 cells of A contain all the elements that were originally in A[1...j] plus x in sorted order.

b) Use induction and the correctness of PutInPlace() (proved in part a) to prove correctness of InsertionSort(A, n).

Any help appreciated thank you!!