思路分析：通过对直接插入排序算法进行思考，我们可以知道插入排序方式首先需要为要插入的元素找到插入序列中合适的插入位置。通过折半（（low+high）/2=mid）的方式，凭借一个mid来使得我们通过二分插入区的方式，不断缩小插入的区域，直到low>high时，我们即可找到元素的插入位置high+1。此种方式在时间复杂度上仍和直接插入排序算法处于同一个等级，但由于使用了折半的方式，所以在为插入元素寻找插入位置时会更加高效（尤其在数据量较大时）。

时间复杂度：最坏情况（整个序列逆序时）时间复杂度为O(n2)，最优情况（整个序列初始顺序，从大到小时）时间复杂度为O(nlog2n)，平均情况时间复杂度为O(n2)。

源代码：

void BinaryInsertSort(int R[],int n) {
    int i, j, low, mid, high, temp;
    for(i = 1; i < n; i++) {
        low = 0;
        high = i - 1;
        temp = R[i];
        while(low <= high) {//找到合适的插入位置high+1，如果中间位置元素比要插入元素大，则查找区域向低半区移动，否则向高半区移动
            mid = (low + high) / 2;
            if(R[mid] > temp)
                high = mid - 1;
            else
                low = mid + 1;
        }
        for(j = i-1; j >= high+1; j--) {//high+1后的元素后移
            R[j+1] = R[j];
        }
        R[j+1] = temp;    //将元素插入到指定位置
    }
}

例子：int[] arr={5,2,6,0,9};经行折半插入排序

图解：

课后习题

【2012年真题】对一待排序序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是（）。 
A．排序的总趟数 
B．元素的移动次数 
C．使用辅助空间的数量 
D．元素之间的比较次数 

参考答案：D
答案解析：考查折半插入和直接插入的区别。 
折半插入排序与直接插入排序都是将待插入元素插入前面的有序子表，区别是：确定当前记录在前面有序子表中的位置时，直接插入排序是采用顺序查找法，而折半插入排序是采用折半查找法。排序的总趟数取决于元素个数 n，两者都是 n-1 趟。元素的移动次数都取决于初试序列，两者相同。使用辅助空间的数量也都是 O(1)。折半插入排序的比较次数与序列初态无关，为 O(nlog2n)；而直接插入排序的比较次数与序列初态有关，为 O(n)~O(n2)。