title: Improving worst-case running time of insertion sort using binary search
body: <p>The while loop uses linear search to scan backwards. However, we know that the array within the while loop is already sorted. So we can replace the linear search with binary search instead so that O(n) will change to O(lg n). However, my take on this is that it won't contribute to reducing the overall time because we would still have to move the elements one index forward which will always take (number of backward steps(n)) times. So overall, the running time stays O(n^2) and there is no way to achieve O(n lg n) for this case. Please tell me if I am approaching this in a wrong way.</p>
  
  <pre><code>INSERTION-SORT(A)
  
   for j = 2 to length[A]
    do key = A[j]
       i = j - 1
  
    while i &gt; 0 and A[i] &gt; key
      A[i+1] = A[i]
      i = i - 1
  
    A[i+1] = key
  </code></pre>