In our discussion of mergesort, we talked about a method for merging two sorted arrays of size n/2. It repeatedly compares the lowest unused element in array A with the lowest unused element in array B, and chooses the one that is lower. To accom- plish this, it has to do n-1 comparisons, and it has an overall running time of O(n). For this question, suppose that you have k sorted arrays, each with p elements, and you want to combine them into a single sorted array of kp elements. (a) Here is one strategy: Use the merge method described above to merge the first two input arrays (of size p) into an array of size 2p. Then use the same method to merge that new array of size 2p with the third input array of size p) to form an array of size 3p. Continue this until you eventually merge an array of size (k 1)p with an array of size p to form your sorted array of kp elements. What is the time complexity of this algorithm, in terms of k and p? Choose one of the options below, and explain your answer. i. (kp) ii. (kp) iii. (kpa) iv. (kp) v. (k log p) vi. (p log k) vii. (kp log k) viii. (kplog p) In your explanation, you should express the total number of comparisons required in all of the merge operations described above as a sum and then solve the sum exactly. (b) Design a more efficient solution to this problem, using a divide-and-conquer approach. Provide pseudocode for how your algorithm would work and then use a recursion tree analysis to determine the asymptotic running time of the algorithm, in terms of e. (To simplify your analysis, you can assume that k is a power of 2.) For full marks, your algorithm must be more efficient than the algorithm de scribed in part (a).] In our discussion of mergesort, we talked about a method for merging two sorted arrays of size n/2. It repeatedly compares the lowest unused element in array A with the lowest unused element in array B, and chooses the one that is lower. To accom- plish this, it has to do n-1 comparisons, and it has an overall running time of O(n). For this question, suppose that you have k sorted arrays, each with p elements, and you want to combine them into a single sorted array of kp elements. (a) Here is one strategy: Use the merge method described above to merge the first two input arrays (of size p) into an array of size 2p. Then use the same method to merge that new array of size 2p with the third input array of size p) to form an array of size 3p. Continue this until you eventually merge an array of size (k 1)p with an array of size p to form your sorted array of kp elements. What is the time complexity of this algorithm, in terms of k and p? Choose one of the options below, and explain your answer. i. (kp) ii. (kp) iii. (kpa) iv. (kp) v. (k log p) vi. (p log k) vii. (kp log k) viii. (kplog p) In your explanation, you should express the total number of comparisons required in all of the merge operations described above as a sum and then solve the sum exactly. (b) Design a more efficient solution to this problem, using a divide-and-conquer approach. Provide pseudocode for how your algorithm would work and then use a recursion tree analysis to determine the asymptotic running time of the algorithm, in terms of e. (To simplify your analysis, you can assume that k is a power of 2.) For full marks, your algorithm must be more efficient than the algorithm de scribed in part (a).]
