Merger Sort algorithm

Problem 1 (30 points): Consider mergesort as discussed in class. Instead of dividing the set of numbers into two nearly equal parts, we can partition the set of n numbers into three nearly equal parts containing 1 and In 2 numbers, sort each part separately and then combine them together into one sorted list. (a) 10 points] Write the pseudocode of the combining algorithm (b) 120 pointsl Analyze the running time (or, equivalently, the number of comparisons, where a comparison is the act of comparing two numbers) made by this new version of mergesort in the worst case. A correct answer should give the recurrence, explain why it is correct and then present its solution. Try to get as tight a bound as you can. Excessively loose bounds on the number of comparisons will incur a loss of most points for this problem. For simplicity. you may assume that n is a multiple of 3 (hence, you could just write n/s instead of-'/31 or