Part 1. (10 points) Sorting algorithms Answer each of the parts in English (not code or pseudocode). Each subpart requires at most 2-4 sentences to answer. Answers significantly longer than required will not receive full credit (a) (3 points) Recall that merge sort works by taking an array, splitting it into two pieces, recursively sorting both pieces, then combining both pieces in O (n) time. Suppose we split the array into three equally sized pieces instead of two. And after we finish recursively sorting each of the three pieces, we first merge two of the three pieces together, then we merge that with the third piece to get the final sorted result. i. Write the recurrence for this variation of merge sort ii. Use the master theorem to give an asymptotic bound for this variation of merge sort. iii. Compare the recurrence and bound of this variation with that of the standard merge sort. Is this variation better or worse than the standard merge sort? Justify your answer (b) (4 points) Suppose you are designing a search aggregator, which for a given query fetches search results from two different search engines and presents an intersection of the two search results. Here is a simplified version of this problem: Given two sorted integer arrays of lengths m and n, return a new array witlh elements that are present in both input arrays. The input array may contain duplicates, but there should be no duplicates in the output array. For example, if the input arrays are [17, 23, 23, 35, 43, 47, 69, 78, 80, 84, 84, 86] and [23, 35, 50], the output array should be [23, 35] i. Describe a brute force solution. What is the big-O time complexity of this brute solution? ii. Describe a solution that has O (mlogn) time complexity iii. Describe a solution that has O (m +n) time complexity iv. Between subparts ii and iii above, is one solution always better than the other (in terms of runtime)? If yes, which one and why? If no, describe the situation (in terms of m and n) when one is better than the other. (c) (3 points) You're given an array where each element is an (age, name) pair representing guests at a DC- Marvel Universe party in Shire. You have been asked to print each guest at the party in ascending order of their ages, but if more than one guests have the same age, only the one who appears first in the array should be printed. For example, if the input array is [(23, Noah), (2000, Gandalf), (50, Frodo), (47, Emma), (23, Sophia), (83200, Superman), (23, Alice), (47, Madison), (47, Mike), (150, Dumbledore)] the output should be (23, Noah) (47, Emma) (50, Frodo) (150, Dumbledore) (2000, Gandalf) (83200, Superman) Describe a solution that takes O (1) space in addition to the provided input array. Your algorithm may modify the input array. This party has some very old guests and your solution should still work correctly for parties that have even older guests, so your algorithm can't assume the maximum age of the partygoers Give the time complexity of your solution