2. (advanced) Let's slightly tweak Merge Sort. Instead of partitioning the array into two subarrays, we will do into three subarrays of an (almost) equal size. Then, each recursive call will sort each subarray, and we will merge the three sorted subarrays. Assuming that merging can be done in O(n) time, write a recurrence for the running time of this new version of Merge Sort, and solve it. 3. (basic) Solve T(n)=4T(n/2)+(n) using the recursion tree method. Cleary state the tree depth, each subproblem size at depth d, the number of subproblemsodes at depth d, workload per subproblemode at depth d, (total) workload at depth d