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 , and 2numbers, sort each part separately, and then combine them together into one sorted list. (a) 10 points] Write the pseudocode of the combining algorithm. (b) 20 points] 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 'i/s instead of or