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[j] into the sorted sequence A[1j1]. i=j1 while i>0 and A[i]> key A[i+1]=A[i] i=i1 A[i+1]=key 2. Rewrite the INSERTION-SORT procedure to sort into nonincreasing instead of nondecreasing 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)={22T(n/2)+nifn=2,ifn=2k,fork>1 is T(n)=nlgn