为何普遍认为二分插入排序比直接插入排序更快？技术疑问探讨

直接插入排序实现 #

void insertion_sort(int a[], int n) {
    for (int i = 1; i < n; i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
}

二分插入排序实现 #

void insertion_sort(int a[], int n) {
    for (int i = 1; i < n; i++) {
        int key = a[i];
        int mid = upper_bound(a, a + i, key) - a;
        for (int j = i - 1; j >= mid; j--) a[j + 1] = a[j];
        a[mid] = key;
    }
}

网上教程普遍认为二分插入排序比直接插入排序更快，理由是二分查找的效率高于顺序查找，但我对此存疑。

直接插入排序在顺序查找插入位置的同时，就完成了元素的移动；而二分插入排序需要花费O(log i)时间找到插入位置，之后还要单独进行元素移动。单看循环内部逻辑，二分插入排序反而比直接插入排序多了O(log i)的查找耗时，那为什么多数人觉得前者更快？

核心原因：比较操作成本远低于移动操作 #

插入排序的耗时主要由元素比较和元素移动两部分构成。直接插入排序的顺序查找过程中，每一次比较失败都要伴随一次元素移动；而二分插入排序的比较操作仅用于定位插入位置，次数是O(log i)，远少于直接插入排序最坏情况下的O(i)次比较。

虽然二分插入排序多了单独的查找步骤，但CPU执行比较操作的开销远小于内存读写（元素移动）。实际运行中，减少大量比较操作带来的收益，会抵消甚至超过二分查找的额外开销，最终整体性能更优。

不同场景的表现差异 #

• 最坏场景（完全逆序数组）：直接插入排序每次要做i次比较，二分插入排序仅需log2(i)次，此时前者的比较耗时会被拉开巨大差距，二分插入排序优势最明显。
• 接近有序的数组：两者的元素移动次数相近，直接插入排序的比较次数也会大幅减少，此时两者性能差距会缩小。
• 大体积元素场景：如果数组元素是占用内存较大的结构体，元素移动的成本会更高，二分插入排序减少比较次数的优势会被进一步放大。

代码实现的细节补充 #

你给出的二分插入排序代码用了upper_bound，这个函数本身基于二分查找实现，时间复杂度确实是O(log i)。而直接插入排序的顺序查找平均要做i/2次比较，当i较大时，i/2和log i的差距会非常显著，这也是二分插入排序在大数据量下更优的关键。

内容的提问来源于stack exchange，提问作者korangar leo