Exercise $5.$ Variations on MergeSort

a$)$ We want to try a variation on MergeSort called MergeSort$3,$ with splits up the input array into $3$ subarrays of length $\frac{n}{3}($or close to it$),$ makes recursive calls to sort them, and then does a $3-$way merge from Homework $4.$

Write the recurrence equation for MergeSort$3,$ and show a call tree for it$.$ Obtain a solution for this recurrence equation, using your favorite method.

b$)$ Generalize your work above to MergeSortK, which splits up the array into $k$ subarrays of length $\frac{n}{k},$ where $k2.$ Note that when $k=2$ we get regular MergeSort and when $k=3$ we get MergeSort $3.$

c$)$ We now have a variation on MergeSort called SillySort which splits up the input array into $2$ subarrays of length $\frac{2}{3}n$ rather than $\frac{1}{2}n.($During the Merge, any duplicate elements are removed.$)$ Write the recurrence equation for MergeSort$3,$ and show a call tree for it$.$ Obtain a solution for this recurrence equation, using your favorite method.

d$)$ Generalize your work above to SillySortK, which uses $2$ subarrays of length $n**\frac{k-1}{k}$ rather than $\frac{1}{2}n,$ where $k2.$ Note that when $k=2$ we get regular MergeSort and when $k=3$ we get SillySort