Question 5 (20%) Here is the pseudo code for INSERTION-SORT INSERTION-SORT(A) 1 for j = 2 to A. length 2 keyAU] 3 Insert AU] into the sorted sequence A[1 ..j -1]. 4 5 while i >0 and Ali] > key 7 i=i-1 8 Ali +11key (a) Observe that the while loop of line 5-7 of the INSERTION-SORT uses linear search to scan through the sorted subarray Al1..j -1]. Can we use a binary search instead to improve the overall worst case running time of insertion sort to ?(n In n)? You must justify your answer. (10 points) (b) INSERTION-SORT can be expressed as a recursive procedure as follows. In order to sort A[1 ..n], we recursively sort A[1..n-1 and then insert A[n] in to the sorted array A[1..n-1]. Write a recurrence for the running time of this recursive version of insertion sort. (10 points)