在直接插入排序的基础上做的改进，直接插入排序在寻找插入位置时是从后到前依次比较，直到找到插入位置。而折半插入排序在寻找插入位置时，先与有序序列中的中间位置R[mid]进行比较，如果比中间位置上的记录大，则在R[mid+1…N]中寻找，继续与右区间的中间记录进行比较；如果比中间位置上的记录小，则在R[0…mid-1]中寻找，继续与左区间中的数据进行比较。
typedef int datatype; int BinaryInsertionSort(datatype *array, int size) { int i, j, low, high, mid; int temp; if(array == NULL) { return -1; } for(i = 1; i < size; i++) { low = 0; high = i-1; temp = array[i]; //跳出循环时low为插入位置 while(low <= high) { mid = (low + high) / 2; //若比中间记录小，则去左区间查找 if(array[mid] > temp) { high = mid - 1; } else { //否则去右区间查找 low = mid + 1; } } //将插入位置到待插入元素的位置上的元素整体向后移动一个位置 for(j = i; j > low; j--) { array[j] = array[j-1]; } array[low] = temp; } return 0; }