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:

1. A linear search to scan (backward) through the sorted sub-array to find the proper position for $$key$$.
2. 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)$$.