使用二分搜索改进插入排序的最坏情况运行时间

while 循环使用线性搜索向后扫描。但是，我们知道 while 循环中的数组已经排序。所以我们可以用二分查找代替线性查找，这样O(n)就变成了O(lg n)。然而，我对此的看法是，它不会有助于减少总时间，因为我们仍然需要将元素向前移动一个索引，这总是需要 (向后步数 (n)) 次。因此，总体而言，运行时间保持为 O(n^2)，并且在这种情况下无法实现 O(n lg n)。请告诉我我是否以错误的方式处理这个问题。

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

插入排序会推送数组的元素，以便为行中的下一个元素释放空间。
因此，如果您使用二分搜索找到了输入新元素的位置，您仍然需要将该索引之后的所有元素向前推进一步（向右）。
所以给定一个向后排序的数组：10,9,8,7,6,5,4,3,2,1
您需要将 i-1 推到右侧才能插入第 i 个元素（即使您使用二分搜索） - 最坏情况时间：O(n^2)
如果您可以将元素一个接一个地插入到列表中，则不必推送元素，但您必须“付费”以搜索列表中的正确位置（因此在此实现中，W.C.T 是 O (n^2))。

这个问题的解决方案是使用列表和数组之间的某种协同作用，这样您就可以在 O(1) 时间内到达第 i 个元素（如数组中一样），并且可以将新元素推送到给定位置（例如在索引 j) 在 O(1) 时间内（如列表） - 如果你成功了，我相信你将赢得永恒的荣耀！