仅末尾元素失序的已排序数组排序，插入排序是否为最快算法？

先说结论：这种场景下插入排序不是可使用的最快排序方案。

场景特性说明 #

该场景属于典型的「仅单元素失序的近有序数组」：前n-1个元素已经完全有序，只有末尾1个元素位置错误，参考示例如下：

[1, 3, 5, 6, 7, 9, 2]

插入排序的实际开销 #

插入排序处理该场景时，需要从末尾元素开始向前逐个比对，遇到比当前元素大的就交换位置。最坏情况（比如末尾元素是整个数组的最小值）下需要完成n-1次比较和n-1次交换操作，时间复杂度为O(n)。

更优的处理方案 #

因为前n-1个元素是完全有序的，我们可以用效率更高的逻辑处理：

1. 用二分查找定位末尾元素应该插入的正确位置，这一步仅需要*O(logn)*的比较开销
2. 将插入位置到倒数第二位的所有元素统一向后移动一位
3. 把原本的末尾元素放到查找到的插入位置即可

这个方案的元素移动开销和插入排序一样是O(n)，但比较操作的开销从O(n)降到了O(logn)，整体常数开销远低于插入排序，实际运行速度更快，且同样支持原地排序，不需要额外的空间消耗。

内容的提问来源于stack exchange，提问作者João Pires