用二分查找的方式在前部找该插入的位置，由于向量需要移动元素，所以无法优化最坏情况下的时间复杂度。
最好情况下，向量原本有序，折半插入排序需要 $O(nlogn)$ 时间，插入排序需要 $O(n)$ 时间。
插入排序一轮无需移动的概率为 $\frac{1}{k}$ (每个元素概率均等作为最大值)，于是，无需移动的轮数的期望为调和级数，为 $\Theta(logn)$，相对 $n$ 轮的循环次数可以忽略不计。
同写在逆序对中的结论。
习题解析[3-11]c
当插入排序轮到 $A[j]$ 时，前方比 $A[j]$ 大的元素依次排在 sorted 部分的末尾，需要比较的次数为前面比 $A[j]$ 大的元素的个数。也就是 $(A[x], A[j])$ 形式的逆序对。 $(A[j], A[x])$ 形式的逆序对轮到 $x$ 的轮次时计数。
所以，有效的比较次数恰为总逆序对数。
不过，由于代码要再往前比一个位置才知道此轮要结束，比较次数不能完全说恰好就是 $I$ ，只能说是 $O(n + I)$