Observe that the

whileloop 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:

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)\).