== 1 == Write the pseudo-code of the procedure MERGE-2 that we have discussed in class, and compute its running time. MERGE-2(L,R) COST TIMES let A[1 ... (L.length + R.length)] be a new array c1 1 i = 1 c2 1 j = 1 c3 1 for k = 1 to A.length c4 (n+1) if L[i] <= R[j] c5 n A[k] = L[i] c6 n1 (this is L.length) i = i + 1 c7 n1 else A[k] = R[i] c8 (n - n1) j = j + 1 c9 (n - n1) where n = A.length, and n1 = L.length. The line "A[k] = L[i]" and the next are executed n1 times because eventually all the elements of L are picked. The line "A[k] = R[i]" and the next are executed for each element of R, that is, (n - n1) times. Although the first line is executed 1 time when presented in pseudo-code, it is more realistic that the cost of creating that array depends on n, but we do not model that. T(n) = c1*1 + c2*1 + c3*1 + c4*(n+1) + c5*n + c6*n1 + c7*n1 + c8 * (n - n1) + c9 * (n - n1) = (c4 + c5 + c8 + c9)*n + c1 + c2 + c3 + c4 + (c6 + c7 - c8 - c9)*n1 == 2 == Use MERGE-SORT to order the sequence <31, 41, 59, 26, 41, 58, 28> Show how MERGE-SORT works on this sequence by showing a tree of calls as we have seen in class. See MergeSort.png on the course website.