Insertion sort is one of the fastest algorithms in practice for sorting an array of length n when n is small. Its worst-case running time is O(n2), however, so for large n merge sort will be faster in the worst case as it runs in O(n log n) time. Consider the following hybrid sorting algorithm, which tries to combine the best features of insertion sort and merge sort. Suppose we divide the sorting problem into subproblems as in merge sort, but use insertion sort to solve a subproblem once it is small enough. More precisely, suppose we divide the input array into dn/ke lists of length at most k, sort each list using insertion sort, and then merge them into one sorted list, where k is a parameter. The following questions analyze the running time of this hybrid algorithm.
A) Show that (n/k] lists, each of length at most k, can be sorted by insertion sort in (nk) worst-case time.
B) Show that the sorted sublists from Part (a) can be merged into one sorted list in (n log(n/k)) worst-case time.
C) By Parts (a) and (b), the hybrid sorting algorithm runs in worst-case time (nk + n log(n/k)). We would like to choose k as a function of n so that the worst-case order of growth for this hybrid algorithm is no worse than the order of growth for merge sort. What is the fastest rate of growth of k for which this holds?
Hint: Answering this requires two steps: (1) coming up with a function f(n) such that if k= (f(n)), the hybrid algorithm runs in O(n log n) time; and (2) show- ing that if k=w(f(n)), the hybrid algorithm runs in wan log n) time.)