Consider a modification to merge sort in which $\frac{n}{k}$ sublists of length $k$ are sorted using

insertion sort and then merged using the standard merging mechanism $($i$.$e$.$ you only do

insertion sort at one level of recursion tree$),$ where $k$ is a value to be determined.

$($a$)$ Show that the insertion sort can sort the $\frac{n}{k}$ sublists each of length $k$ in $(nk)$ worst$-$case

time.

$($b$)$ Show that the $\frac{n}{k}$ sublists can be merged in $(nlg(\frac{n}{k}))$ worst$-$case time. Hint: Assume

that at the level of the recursion tree where we start merging, we have $\frac{n}{k}$ sublists. How

many levels are there above the level we start merging if that level has $\frac{n}{k}$ sublists $($i$.$e$.$ sub

arrays$)$ and what is the cost of merging in each of these levels?

$($c$)$ Given that the modified algorithm runs in $(nk+nlg(\frac{n}{k}))$ worst$-$case time, what is the

largest value of $k$ as a function of $n$ and in $-$notation for which the modified algorithm has

the same running time as merge sort in $-$notation? Hint: Which value of $k$ makes

$\{$:$nlg(\frac{n}{k}))=(nlgn)?$ Show that $k=(lgn)$ works.

$($d$)$ How should we choose $k$ in practice? Hint: consider the list $($i$.$e$.$ array$)$ lengths for which

insertion sort is better than merge sort, which is a range of integers to choose from. Then

consider which of these values is the best option to start with when combined with merge

sort. Can we choose $k$ as the largest list length on which insertion sort is faster than merge

sort?