注意到下面伪代码INSERTION-SORT的第5~7行的while循环采用一种线性查找来（反向）扫描已排好序的子数组A[1..j-1]。我们可以使用二分查找来吧插入排序的最坏情况总允许时间改进到)
。
INSERTION-SORT(A) for j = 2 to A.length key = A[j] // Insert A[j] into the sorted sequence A[1..j-1] i = j - 1 while i > 0 and A[i] > key A[i + 1] = A[i] i = i - 1 A[i + 1] = key
