Merge Sort with a Constant-Size Insertion-Sort Cutoff

The idea — coarsening merge sort

Plain merge sort recurses all the way down to subarrays of size $1$. Coarsening (CLRS Problem 2-1) stops the recursion early: once a subarray shrinks to a fixed small size $k$, you no longer split it — you sort that block directly with insertion sort, which is fast and cache-friendly on tiny inputs. The merges then rebuild the array from the sorted blocks as usual.

The whole result hinges on one question: is $k$ a constant, or does it grow with $n$?

The two phases and their cost

Split the work into the insertion-sort phase (sorting the bottom blocks) and the merge phase (combining them upward).

1. Insertion-sort phase. A block of size $k$ costs $\Theta(k^{2})$ in the worst case. There are $\dfrac{n}{k}$ blocks, so the total is

$\frac{n}{k}\cdot\Theta(k^{2})=\Theta(nk).$

2. Merge phase. Merging starts at blocks of size $k$ (not size $1$), so the recursion tree is shortened: instead of $\log_2 n$ levels it has only $\log_2\!\dfrac{n}{k}$ levels. Each level still does $\Theta(n)$ merging work, giving

$\Theta\!\left(n\log\frac{n}{k}\right).$

Total:

$T(n)=\Theta\!\left(nk + n\log\frac{n}{k}\right).$

Reading the formula — the role of $k$

When $k$ is a constant, $\log\dfrac{n}{k}=\log n-\log k=\log n-O(1)=\Theta(\log n)$ and $nk=\Theta(n)$, so

$T(n)=\Theta(n)+\Theta(n\log n)=\Theta(n\log n).$

The cutoff is invisible to the asymptotics — it only improves the hidden constant (which is why real libraries do it). The cutoff is provably worthwhile right up to $k=\Theta(\log n)$; beyond that the quadratic insertion-sort term takes over and degrades the bound.

How to apply (recipe)

1. Identify the cutoff size $k$ and ask whether it is constant or a function of $n$.
2. Insertion phase $\to\Theta(nk)$; merge phase $\to\Theta\!\left(n\log\frac{n}{k}\right)$.
3. Add them and simplify, treating any constant $k$ as $O(1)$.

Mini-example

Merge sort that switches to insertion sort on every subarray of size $\le 20$. Here $k=20$ is constant: insertion phase $=\Theta(20n)=\Theta(n)$, merge phase $=\Theta(n\log\frac{n}{20})=\Theta(n\log n)$, so the algorithm is still

$T(n)=\Theta(n\log n).$

Exam trick: A fixed cutoff ("sort blocks of $20$ / of $100$ with insertion sort") is a constant — it cannot change the $\Theta$. The answer stays $\Theta(n\log n)$. Only a cutoff that scales with $n$ matters: $k=\Theta(\log n)$ is the break-even point (still $\Theta(n\log n)$), and anything larger makes the insertion-sort term $\Theta(nk)$ dominate.