In the insertion sort there is a while loop use linear searc

In the insertion sort there is a while loop use linear search to scan (backward) through the sorted subarray A[1..j-1] Can we use binary search instead to improve the overall worst-case running lime of insertion sort to theta (lgn)?

Solution

Let\'s say you use binary search to find the position. But think about this, once done, next step would involve shifting all the elements after it to right which means that it would have to swap all those elements one by one again anyways. And it is the same number of swaps as there were originally and worst case time will be linear. So, in conclusion:

So, in short NO.