Modified merge Sort Algorithm

Question

Describe a modified merge sort algorithm, in which a given sequence is split into split into three sub-sequences of equal size approximately one-third. Analyze asymptotically the time complexity of your algorithm. How to solve this?

Answer 1

This is probably your homework but i would recommend that you do read chapter 2 from Cormen , Lierson and Rivest .

solve this recurrence relation - T(n) = 3T(n/3) + O(n)

Every problem is subdivided into 3 sub-problems and contain n/3 part of the original data. Apply masters theorem to it and you will find that the answer is 0( n*log(n) ).

Note - here logarithm is of base 3 .