Consider a variant of Merge Sort, namely Ternary Merge Sort (TMS): To sort an array A of size n, A is split into three sub-arrays of size n/3 each. Then, TMS is recursively called on each sub-array. A merge step merges all three sorted sub-arrays into a single sorted array 3. Assume that n is not a power of 3. Expand the input array A to have n' elements, where n' is a power of 3. Consider the expanded array A' of size n': Obviously n' 2 n; let the first n elements of A' be equal to the n elements of A. What values would you choose for the remaining n'- n elements of A' in order to be able to run TMS on A' and immediately get a sorted list of the elements in the original array A? 4. Prove an appropriate upper bound for the running time of the TMS algorithm given an input of size 5. How does the running time of TMS on A' compare to its running time on A? Explain why having an 6. Explain why any assumption of the form that n is a power of a constant (say, n is a power of two, n'; the bound must be in terms of n. assumption that n is a power of three is without loss of generality three, four, etc.) is also without loss of generality. No need to present a detailed proof, just an outline of the overall argument is sufficient