【基本思想】

在直接插入排序中，每趟插入过程都进行了两项工作：

从有序子表中查找待插入元素应被插入位置
给插入位置腾出空间，将待插入元素复制到表中插入位置

可以看出，上述过程总是边比较边移动元素，针对这一过程，进行改进，即将比较与移动分离，先查找出元素的待插入位置，再统一的移动待插入位置后的所有元素

由于有序区是顺序表，因此可以采用折半查找来寻找插入位置

【性能分析】

折半插入排序仅适用于顺序存储方式，是在直接插入排序的基础上进行的改进，其仍是一种稳定排序算法

在排序过程中，仅需一个辅助空间，作为待插入记录的暂存单元，因此空间复杂度为：

$O(1)$

由于折半查找的过程减少了元素的比较次数，该比较次数与待排序表的状态无关，仅与 $n$ 的大小有关，故而查找的时间复杂度为 $O(nlog_2n)$，但元素的移动次数没有改变，为 $O(n^2)$，因此，折半插入排序的时间复杂度仍为：

$O(n^2)$

虽然折半插入排序与直接插入排序的时间复杂度相同，但对于数据量不大的情况，折半插入排序往往能表现出较好的性能

【实现】

void insertBinarySort(int a[], int n) {
    for (int i=2; i <= n; i++) { //n-1趟比较，a[2]~a[n]依次插入
        int temp = a[i]; //暂存a[i]
        int left = 1, right = i-1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (a[mid] > temp)
                right = mid - 1;
            else
                left = mid +1;
        }
        for (int j = i - 1; j >= right + 1 ;j--) //记录后移
            a[j+1] = a[j]; 
        a[right+1] = temp; //复制到插入位置
    }
}