16 views

Observe that the while loop of the INSERTION-SORT procedure uses a linear search to scan (backward) through the sorted subarray $A[i\dots 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)$?

| 16 views

Although by using Binary search instead of using linear search, the search time for finding the correct position for the element will decrease (becomes $\Theta(log\ n)$) but the swaps that we need to do to create the place for inserting that element will not change. So the overall time complexity will not be effected.