Insertion sort on small arrays in Merge Sort

Question

Quick question on the wording of the question from CLRS Ch2 Problems. The question goes as follows:

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 can make it faster in practice for small problem sizes on many machines. Thus, it makes sense to coarsen the leaves of the recursion by using 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.

My question is: shouldn't there be $k$ sublists each of length $n/k$? The other way around is stated in the question. Because in merge sort, we keep halving the array, thus producing twice the number of arrays as in the previous level. Hence, each sublist is of length $n/k$ and we have $k$ of such sublists. Why does the question mention this the other way around?

Answer 1

The idea most probably is to chose sublist size $k$ such that merge sort likely is faster for bigger problem instances and insertion sort for smaller ones.
$\lceil s = n/k\rceil$ sub-lists may be suboptimal for merging lists of disparate size later on.
One alternative is splitting into $2^{\lfloor\log_2{n/k}\rceil}$ lists.

Answer 2

The proposed algorithm has the following structure. On an input of length $n$:

• If $n$ is large, then divide the input into two parts of sizes $\lfloor n/2 \rfloor$ and $\lceil n/2 \rceil$, sort of each of them recursively, and then merge them.
• If $n$ is small, then instead use insertion sort.

When should we switch to insertion sort? When the list size is smaller than some constant $k$.

If you think of the entire recursion tree, then we switch to insertion sort when having $n/k$ sublists of length $k$, and not the other way around. Switching when we have $k$ sublists of length $n/k$ would mean switching at a constant recursion depth, which makes little sense here.