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.
INSERTION-SORT(A) for j = 2 to length[A] do key = A[j] i = j - 1 while i > 0 and A[i] > key A[i+1] = A[i] i = i - 1 A[i+1] = key
Anyone one of you who have studied algo analysis should find it interesting.