插入排序&折半查找

插入排序的时间复杂度不必多说，O(n^2)，但是如果把寻找插入位置的操作用折半查找来代替，那会不会优化到O(nlgn)？
不会，因为寻找到插入位置后还是要做插入操作，而元素的移动总数还是一样的，所以在理论上性能虽然会有所改进，但是改变不了插入排序的先天不足。
但是归并排序在把序列划分到足够小之后用插入排序来完成底层的排序工作还是挺有吸引力的，O(nlg(n/k))，如果是对k个元素的子序列插入排序的话。