Insertion sort on small arrays in merge sort Although merge sort runs in ?(n lg
ID: 3711038 • Letter: I
Question
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 ?
Explanation / Answer
a. Each sublist with length k takes ?(k^2) worst-case time using Insertion-Sort. To sort n/k such sublists, it takes n/k × ?(k^2) = ?(nk) worst-case time.
b. Merging n/k sublists into n/2k sublists takes ?(n) worst-case time.
• Merging n/2k sublists into n/4k sublists takes ?(n) worst-case time
• .......
• Merging 2 sublists into one list takes ?(n) worst-case time
• We have lg(n/k) such merges, so merging n/k sublists into one list takes ?(n lg(n/k)) worst-case time.
c. In order for ?(nk + n lg(n/k)) = ?(n lg n), either nk = ?(n lg n) or n lg(n/k) = ?(n lg n). From the above two possibilities, we know the largest asymptotic value for k is ?(lg n).