2. (20 points) We will soon study an algorithm called merge sort. Merge sort may be generalized to break the sorting task into any fixed number of subproblems per recursive call; in this problem, we will consider 3-way merge sort, which solves 3 subproblems per recursive call. The runtime of 3-way merge sort may be expressed as T(n) = 3T(n/3) + n with base case T(1) 1. (3 points) Sketch a recursion tree representing the recurrence above. Please sketch at least 3 levels of the recursion tree plus the base level. You may assume n is a power of 3 a. (7 points) Based on your recursion tree, what is the closed form solution of the recurrence T(n) 3T(n/3)+n? b. (3 points) Given your solution, what is the strongest statement we can make about the asymptotic complexity of 3-way merge sort? c. T(n) = d. (7 points) Suppose a parallel implementation of 3-way merge sort can reduce the runtime of the algorithm to T(n) = T(n/3) + c with base-case time still T(1)1. What is the strongest statement we can make about the asymptotic complexity of this