Problem $18.$ Consider a modified version of MergeSort, which divides the array into $6($as equally$-$sized as possible$)$ partitions $($Recall: Standard MergeSort partitions the array into $2-$equal sized sets$).$ This variation of MergeSort is called the $$k$-$way$$ MergeSort, where k $=6.$ Instead of dividing the input array into two sub$-$ arrays, $6-$way$$ MergeSort divides the array into six subarrays, sorts them recursively, and then call a $6-$way$$ Merge which combines four sorted arrays into one sorted array.

Note: This only occurs for array of sizes greater than or equal to $6.$ For array of size less than $6$ assume that there is another sorting algorithm that sorts the elements in $\backslash$theta $($log n$)$ time.

Do the following two parts of the question.

$1.$ Write down the recurrence relation for the runtime of this modified version of $6$way$$ MergeSort. Justifyyour recurrence relation in $12$ sentences.

Answer.

$2.$ Solve your recurrence relation from part $(1),$ by any method you choose. Show your work. Find a function f $($n$)$ such that the runtime T $($n$)$ is T $($n$)=$ O$($f $($n$)).$

Answer.