Recall MergeSort, in which a list is sorted by first sorting the left and right halves, and then

merging the two lists. We define the $3-$MergeSort 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.

Write a recurrence for $T(n),$ the worst$-$case run time for $3-$MergeSort on any input containing

n elements.