Observe that the while loop of lines 5–7 of the 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:

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 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 insert 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)$.

If you have any question or suggestion or you have found any error in this solution, please leave a comment below.