(20%) Run the iterative version of insertion sort on an array containing the following elements: 34 72 81 19 27 36 50 Use brackets to indicate the portion of the array that's already sorted, as in the second half of Figure 3.8. (20%) Run merge sort on an array containing the following elements: 34 72 81 19 27 36 50 42 Show the entire recursion, as in Figure 3.13 of the notes. (20%) Consider the recurrence relation T(n) = T([n/2]) + T([n/2]) + bn^2, if n greaterthanorequalto 2 T(1) = (1) Assuming that n is a power of 2, use a recursion tree to solve this recurrence. (20%) Use induction to prove that the upper bound you obtained in the previous exercise holds in the general case, when n is not necessarily a power of 2. (Do only the upper bound.)