PART $1-$ MergeSort, but now in thirds $(10$ pts$)$

MergeSort originally merges exactly $2$ equal$-$length sorted arrays at the final Combine step as in

Divide and Conquer, which we denote as Merge$2().$ However, per request we now want to split

the input array in $3$ equal subarrays and then recursively call MergeSort on all $3$ subarrays. We

then need to implement a new merge operation Merge $3()$ to combine $3$ sorted subarrays.

A$.$ How would you implement this new Merge$3()$ routine? You may show us the

pseudocode, or simply describe how you would perform the tweak from Merge$2()$ in

plain English, in no more than $4$ full sentences. $(6$ pts$)$

B$.$ And what is the overall Big$-$O$-$of$-$N time complexity for this updated version of MergeSort

that now uses Merge$3()?(4$ pts$)$ Hint: You could either present the divide$-$merge tree,

or work with the recurrence analysis expression in terms of $T(n).$