Question

The multi-merge sort algorithm (M&M sort) works like merge sort, except that instead of dividing the array into 2 partitions, it divides the array into p partitions. It recursively sorts each of the p partitions and then merges the results doing a p-way merge (except, of course, for the base case of a singleton or empty array). (a) Write the recurrence for T(n) for M&M sort for the case where p is a constant. Then, give a closed-form solution to the recurrence using the Master Theorem, and note which case applied. (b) Now assume that p is not a constant, but rather p(n) = n/10. Rewrite T(n) for this case. Then, give a closed form solution. Use the Master Theorem if it applies, or any other means of arriving at the result.

Answer 1

(a) Doing a p-way merge sort requires breaking the array into p partitions at each step. So, in each step we need to solve p problems of the size n/p, and then merge them. Therefore it takes T(n) time to sort an array of length n where
and where c is a constant.

This can be solved using the Master's Theorem, we since the relation is of the form where and . Here the function f(n) is in =. So, .

(b) If we divide the array into n/10 partitions at each step, where n is the length of the array at the previous step, then at each step we solve n/10 problems each of length 10, and merge them. Therefore to sort an array of length n it takes T(n) time where and where c and c' are constants. The solution of this recurrence is not possible using Master's theorem as it is not in the form where a and b are constants. But since T(10) is a constant we got the closed form as T(n)=c'n.