== 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.