Observe that the while loop of lines 5–7 of the
INSERTION-SORTprocedure in Section 2.1 uses a linear search to scan (backward) through the sorted sub-array . Can we use a binary search (see Exercise 2.3-5) instead to improve the overall worst-case running time of insertion sort to ?
Let’s take a look at the loop in question:
1 2 3 while i > 0 and A[i] > key A[i + 1] = A[i] i = i - 1
This loop serves two purposes:
- A linear search to scan (backward) through the sorted sub-array to find the proper position for
- Shift the elements greater than
keytowards the end to insert
keyin 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 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 .