Here we will study what happens to Merge Sort if we divide the given problem into more than two sub problems. Consider the modification to the Merge Sort procedure that at each step of the recursion, divides the problem of size n into √ n sub problems each of size √ n. In this problem you will analyze the running time of this version of Merge Sort.

• Show how to use the merge procedure for merging two sorted arrays in order to merge √ n sorted arrays each of size √ n. Analyze the run time in O() notation.

• Use the analysis above to write the recurrence relation for the √ n-way merge sort procedure and analyze the run time in O() notation.

• Design a better algorithm for merging √ n sorted arrays each of size √ n. Your algorithm should run in Θ(n log n) time. [Hint: Use divide and conquer]

• Use the faster merging procedure to analyze the new recurrence for the √ n-way merge sort procedure and analyze the run time in O() notation.