2.3

Multiway Merge Sort 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 sub problems each of size v/F1. 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 v/F1 sorted arrays each of size v/7. Analyze the run time in 0() notation.

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

• Design a better algorithm for merging v/F1 sorted arrays each of size v/F1. Your algorithm should run in log n) time.

[Hint: Use divide and conquer]

• Use the faster merging procedure to analyze the new recurrence for the v/ö-way merge sort procedure and analyze the run time in 0() notation.

2.4

• Suppose we want to find the largest two elements in an array with n elements. Clearly this can be solved in O(n) time but we will try to understand the precise constants.

Show that the problem can be solved using at most 2n — 3 comparisons.

Next, show that there is a better way that uses only n + log n — 2 comparisons. You can assume that n is a power 2.

[Hint: Imagine that the n elements are Tennis players and that you are running a tournament among them. In other words, instead of linearly scanning the array use divide and conquer to find the largest element. Then inspect the recursion tree and see if you can quickly find the second largest.]