What is the Invariant of Merge Sort?
2. Analyze Merge Sort Algorithm by finding T(n) the running time
of MERGE-SORT on an input of n values.
3. What is the best-case running time?
4. What is the worst-case running time?

 

MERGE(A, p, q,r) = 1 nq-p+1 2 n2r q 3 let L[1..n + 1] and R[1..n2 + 1] be new arrays 4 for 5 1 to ni L[i] =A[pi-1] 6 for j = 1 to n 7 8 L[n 1] = R[j] = A[q+j] 9 R[n+ 1] = 10 i = 1 11 j = 1 12 for k = p to r 13 14 15 16 if L[i] < R[j] A[k] = L[i] i=i+1 else A[k]R[j] 17 jj+1