Insertion sort on small arrays in merge sort

Although merge sort runs in ?(n lg n) worst-case time and insertion sort runs in ?(n 2 ) worst-case time, the constant factors in insertion sort make it faster for small problem sizes on many machines . Thus, it makes sense coarsen the leaves of the recursion by using insertion sort within merge sort when subproblems become sufficiently small. Consider a modification for merge sort in which n/k sublists of length k are sorted using insertion sort and then merged using the standard merging mechanism, where k is a value to be determined.

a. Show that insertion sort can sort the n/k sublists, each of length k, in ?(nk) worst-case time.

b. Show how to merge the sublists in ?(n lg(n/k)) worst-case time.

c. Given that the modified algorithm runs in ?(nk +n lg(n/k)) worst-case time, what is the largest value of k as a function of n for which the modified algorithm has the same running time as standard merge sort, in terms of ?-notation ?