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.