Problem 6 (5+5+5 points) We have seen in the lecture that in MERGE_SORT, the input array is first split into two halves, each half is sorted recursively, and then, the two sorted halves are merged into a final sorted array. We define the 3_MERGE_SORT algorithm, in which the input array is split into 3 equal length parts (or as equal as possible), each is sorted recursively, and then the three parts are merged to create a final sorted array. (a) Write a recurrence for T(n), the worst-case run time for 3_MERGE_SORT on any input consisting of n elements. (b) Construct the corresponding recursion tree and solve this recurrence for T(n) (Construct it similar to what you have seen for MERGE_SORT during the lecture). (c) Prove your result in part (b) formally using induction