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 subarray \(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)\)?

The worst-case running time for INSERTION-SORT as presented in section 2.1 involves an array that is in reverse-sort order which we know has a running time of \(\Theta(n^2)\). The while loop in question effectively contributes one of the \(n\) values of our run-time, so it seems that we may be able to reduce the worst-case run time by applying INSERTION-SORT. However, this while loop does more than just locate a value. It shifts all of the values one by one as it is searching for the proper location to insert, and thus the worst-case run-time cannot be reduced as we still need to act on each value in our sorted subarray.