1. Consider the following modification to the MergeSort algorithm: divide the input array into fourths (rather...

   

Transcribed Image Text:

1. Consider the following modification to the MergeSort algorithm: divide the input array into fourths (rather than halves), recursively sort each sort each forth, and finally combine the results using a four-way Merge subroutine. i) At each level j = 0, 1, 2, ... of the recursion tree, how many subproblems are there? ii) What is the length each subproblem operates on? iii) How many operations are performed at the jth recursion level? iv) What is the running time of this algorithm as a function of the length n of the input array, ignoring constant factors and lower-order terms? 1. Consider the following modification to the MergeSort algorithm: divide the input array into fourths (rather than halves), recursively sort each sort each forth, and finally combine the results using a four-way Merge subroutine. i) At each level j = 0, 1, 2, ... of the recursion tree, how many subproblems are there? ii) What is the length each subproblem operates on? iii) How many operations are performed at the jth recursion level? iv) What is the running time of this algorithm as a function of the length n of the input array, ignoring constant factors and lower-order terms?