Cormen Edition 3 Exercise 2.3 Question 6 (Page No. 39)

Question

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)$?

Comments

Using Binary-Search in Insertion Sort we can only reduce number of Comparisons,however number of swaps remains same.

$ #Comparisons$ = $\mathcal{O}(n\log(n))$

$ #Swaps$ = $\mathcal{O} (n^{2})$

So,time complexity = $Comparion + Swaps$ = $\mathcal{O}(n\log(n))$ + $\mathcal{O} (n^{2})$ = $\mathcal{O} (n^{2})$

Answer 1

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.