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 = 2 to n key = A[j] // Insert A[] into the sorted sequence A[1.. j - 1]. i = j - 1 while i > 0 and A[i]> key A[i+1] = A[i] i=i-1 A[i+ 1] = key Homework 2 2. Rewrite the INSERTION-SORT procedure to sort into nonincreasing instead of non- decreasing order. 3. Illustrate the operation of merge sort on the array A= 4. Use mathematical induction to show that when n is an exact power of 2, the solution of the recurrence. T(n): 2 if n = 2, 2T (n/2) +n if n = 2k, for k > 1 is T(n) = n lgn.