Consider the Merge-Sort algorithm. Which permutation of the list (1, 2, 3, 4, 5, 6, 7, 8) will elicit the best-case performance (as measured in number of comparisons) between elements in the input list. We do NOT count comparisons to sentinels. Also, answer the same question for worst-case. (the merging subroutine of MS denoted by M).

MS(A, p, r)

1 If p < r

2 q = floor((p+2)/2)

3 MS(A, p, q)

4 MS(A, q+1, r)

5 M(A, p, q, r)