A Hybrid Merge/Insertion Sort Algorithm

Although MergeSort runs in (n lg n) worst-case time and InsertionSort runs in (n2) worst-case time, the constant factors in InsertionSort (including that fact that it can sort in-place) can make it faster in practice for small problem sizes on many machines. Thus, it makes sense to coarsen the leaves of the MergeSort recursion tree by using InsertionSort within MergeSort when subproblems become sufficiently small.

Consider a modification to MergeSort in which n/k sublists of length k are sorted using InsertionSort and are then merged using the standard merging mechanism, where k is a value to be determined in this problem. In the first two parts of the problem, we get expressions for the contributions of InsertionSort and MergeSort to the total runtime as a function of the input size n and the cutoff point between the algorithms k.

(a) Show that InsertionSort can sort the n/k sublists, each of length k, in (nk) worst-case time. To do this:

1. Write the cost for sorting k items with InsertionSort,

2. multiply by how many times you have to do it, and

3. show that the expression you get simplifies to (nk)

(b) Show that MergeSort can merge the n/k sublists of size k in (n lg (n/k)) worst-case time. To do this:

1. draw the recursion tree for the merge,

2. determine how many elements are merged at each level,

3. determine the height of the recursion tree from the n/k lists that InsertionSort had already taken care of up to the single list that results at the end, and

4. show how you get the final expression (nlg(n/k)) from these two values.

Putting it together: The asymptotic runtime of the hybrid algorithm is the sum of the two expressions above: the cost to sort the n/k sublists of size k, and the cost to divide and merge them. You have just shown this to be:

(nk + n lg (n/k)) In the second two parts of the question we explore what k can be.

(c) The bigger we make k the bigger lists InsertionSort has to sort. At some point, its (n2) growth will overcome the advantage it has over MergeSort in lower constant overhead. How big can k get before InsertionSort starts slowing things down? Derive a theoretical answer by proving the largest value of k for which the hybrid sort has the same runtime as a standard (n lg n) MergeSort. This will be an upper bound on k. To do this:

1. Looking at the expression for the hybrid algorithm runtime (nk+nlg(n/k)), identify the upper bound on k expressed as a function of n, above which (nk + n lg (n/k)) would grow faster than (n lg n). Give the f for k = (f(n)) and argue for why it is correct.

2. Show that this value for k works by substituting it into (nk+nlg(n/k)) and showing that the resulting expression simplifies to (n lg n).

(d) Now suppose we have two specific implementations of InsertionSort and MergeSort. How should we choose the optimal value of k to use for these given implementations in practice?