Insertion Sort on Small Arrays in Merge Sort

Although merge sort runs in worst-case time and insertion sort runs in worst-case time, the constant factors in insertion sort make it faster for small . Thus, it makes sense to use insertion sort within merge sort when subproblems become sufficiently small. Consider a modification to merge sort in which sublists of length are sorted using insertion sort and then merged using the standard merging mechanism, where is a value to be determined.

  1. Show that the sublists, each of length , can be sorted by insertion sort in worst-case time.
  2. Show that the sublists can be merged in worst-case time.
  3. Given that the modified algorithm runs in worst-case time, what is the largest asymptotic (-notation) value of as a function of for which the modified algorithm has the same asymptotic running time as standard merge sort?
  4. How should be chosen in practice?

1. Sorting Sublists

For input of size , insertion sort runs on worst-case time, i.e. running time of the form . So, worst-case time required to sort sublists, each of length , with insertion sort:

Now, is an integer significantly smaller than . So, for sufficiently large values of , we can ignore the last two term of . So, .


2. Merging Sublists

We have elements divided into sorted sublists each of length . To merge these sorted sublists to get a single sorted list of length , we have to take 2 sublists at a time and continue to merge them. This will result in steps (If you have problem understanding this statement, refer to Figure 2.5 in page 35 of the chapter text). And in every step, we are essentially going to compare elements. So the whole process will run at .


3. Largest Value of

For the modified algorithm to have the same asymptotic running time as standard merge sort, must be same as .

To satisfy this condition, cannot grow faster than asymptotically (if grows faster than , because of the term, the algorithm will run at worse asymptotic time than ). But just this argument is not enough as we have to check for , the requirement holds or not.

If we assume, ,

is very small compared to for sufficiently larger values of .


4. Practical Value of

To determine a practical value for , we need to calculate the exact running time expressions with proper values for the constant factors and use the method described in Excercise 1.2.2.

If you have any question or suggestion or you have found any error in this solution, please leave a comment below.