Problem 1-2. [10 points] k-Way Merge Sort Merge sort is a divide-and-conquer algorithm based on the idea that merging two sorted subarrays into one large sorted array is possible in linear time. Recall that merge sort divides unsorted input into two equally-sized subarrays, recursively sorts those subarrays, and then merges them. An excited computer scientist named Talan Uring is wondering whether he can modify the merge sort algorithm to sort even faster! In particular, he wants to k-way merge sort. A k-way merge sort divides the input into k equally-sized subarrays. These k subarrays are then recursively sorted and merged into a new array. To merge them, maintain a pointer for each subarray. Each pointer starts at the beginning of its subarray. The algorithm then determines the minimum of the elements pointed to by the k pointers and copies it to the next position in the new array. The pointer to the minimum element is then moved forward by one. This procedure continues until all the pointers are at the end of their subarrays. Note that a 2-way merge sort corresponds to standard merge sort. (a) [3 points] Suppose Talan sets k to 5. Write a recurrence for the 5-way merge sort algorithm. (b) [4 points] Solve the recurrence from (a) using the Master Theorem. How does the running time of this approach compare to standard merge sort? (c) [3 points] Talan now considers setting k to a non-constant value, specifically k = vn where an array of size n is divided into n subarrays to merge. Write a recurrence for n-way merge sort. You do not have to solve this recurrence