为什么使用二进制搜索的插入排序比使用线性搜索的插入排序慢？

Question

为什么使用二进制搜索的插入排序比使用线性搜索的插入排序慢？

使用线性搜索进行插入排序的代码：

void InsertionSort(int data[], int size)
{
    int i=0, j=0, temp=0;

    for(i=1; i<size; i++)
    {
     temp = data[i];
     for (j=i-1; j>=0; j--)
         {
             if(data[j]>temp)
             data[j+1]=data[j];
             else  
                 break;
         }
     data[j+1] = temp;       
    }        
}

使用线性搜索进行插入排序的代码：

void InsertionSort (int A[], int n)
{
    int i, temp;
    for (i = 1; i < n; i++)
    {
        temp = A[i];

        /* Binary Search */

        int low = 0, high = i, k;

        while (low<high)
        {
            int mid = (high + low) / 2;


            if (temp <= A[mid]) 
                high = mid;

            else 
                low = mid+1;
        }

        for (k = i; k > high; k--)
            A[k] = A[k - 1];


        A[high] = temp;
    }
 }

虽然对于平均情况，使用二进制搜索的比较次数= O(nlogn)，使用线性搜索的比较次数= O(n^2)。

​

​

其中原始插入排序为线性搜索排序，修正插入排序为二分搜索排序。

Answer 1

因为在第一种情况下搜索和移动是结合在一起的，而在第二种情况下搜索只是额外的工作。

与移动整数相比，比较整数是很便宜的。考虑到划分，循环开销，在每次循环迭代中采取的条件跳转与未采取的第二次跳转，等等。

PS。实际上，在线性搜索版本中，内部循环通常如下所示：

.L5:
    leaq    -1(%rcx), %rsi
    movl    4(%rdi,%rsi,4), %eax
    cmpl    %eax, %r9d
    jge .L3
    movq    %rcx, %r8
    movq    %rsi, %rcx
    subl    $1, %edx
    movl    %eax, 4(%rdi,%r8,4)
    cmpl    $-1, %edx
    jne .L5
    movq    $-1, %rcx
.L3:

其中jge .L3只执行一次，并且可以合理地预期该分支将被预测为非采用，并且不会对流水线产生有害影响。

至于另一个版本中的内部循环，我不想看它:)

PS。顺便说一句，线性搜索也有更好的局部性，而二进制搜索则到处跳跃。