Question 4: (5+5=10 points) Recall Merge Sort, in which a list is sorted by first sorting the left and right halves, and then merging the two lists. We define the 3-Merge Sort algorithm, in which the input list is split into 3 equal length parts (or as equal as possible), each is sorted recursively, and then the three lists are merged to create a final sorted list. 1. Write a recurrence for T(n), the worst-case run time for 3-Merge Sort on any input containing n elements. 2. Solve this recurrence for T(n). Prove your result formally using the substitution method (i.e., induction). For full credit, you'll need to show both an upper and a lower bound