CLRS Solutions | Exercise 2.3-6

Observe that the while loop of lines 5–7 of the $\textsc {Insertion-Sort}$ procedure in Section 2.1 uses a linear search to scan (backward) through the sorted sub-array $A[1 . . j - 1]$. Can we use a binary search (see Exercise 2.3-5) instead to improve the overall worst-case running time of insertion sort to $\Theta(n \lg n)$?

Let’s take a look at the loop in question:

$$\begin{aligned}5& \quad \textbf {while }i>0\text { and }A[i]>key \\6& \quad \qquad A[i+1]=A[i] \\7& \quad \qquad i=i-1 \\\end{aligned}$$

This loop serves two purposes:

A linear search to scan (backward) through the sorted sub-array to find the proper position for $key$.
Shift the elements that are greater than $key$ towards the end to insert $key$ in the proper position.

Although we can reduce the number of comparisons by using binary search to accomplish purpose 1, we still need to shift all the elements greater than $key$ towards the end of the array to make space for $key$. And this shifting of elements runs at $\Theta(n)$ time, even in average case (as we need to shift half of the elements). So, the overall worst-case running time of insertion sort will still be $\Theta(n^2)$.