Insertion Sort on Small Arrays in Merge Sort

Although merge sort runs in $\Theta(n \lg n)$ worst-case time and insertion sort runs in $\Theta(n^2)$ worst-case time, the constant factors in insertion sort make it faster for small $n$. Thus, it makes sense to use insertion sort within merge sort when subproblems become sufficiently small. Consider a modification to 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.

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

1. Sorting Sublists

For input of size $k$, insertion sort runs on $\Theta(k^2)$ worst-case time, i.e. running time of the form $(ak^2 + bk + c)$. So, worst-case time required to sort $n/k$ sublists, each of length $k$, with insertion sort:

Now, $k$ is an integer significantly smaller than $n$. So, for sufficiently large values of $n$, we can ignore the last two term of $T(k)$. So, $T(k) = \Theta(nk)$.

2. Merging Sublists

We have $n$ elements divided into $n/k$ sorted sublists each of length $k$. To merge these $n/k$ sorted sublists to get a single sorted list of length $n$, we have to take 2 sublists at a time and continue to merge them. This will result in $\log (n/k)$ 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 $n$ elements. So the whole process will run at $\Theta(n \lg (n/k))$.

3. Largest Value of $k$

For the modified algorithm to have the same asymptotic running time as standard merge sort, $\Theta(nk + n \lg(n/k)) = \Theta(nk + n \lg n - n \lg k)$ must be same as $\Theta(n \lg n)$.

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

If we assume, $k = \Theta(\lg n)$,

$^\dagger\lg (\lg n)$ is very small compared to $\lg n$ for sufficiently larger values of $n$.

4. Practical Value of $k$

To determine a practical value for $k$, 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.