【说明】
为了减少直接插入排序关键字的比较次数，本算法使用了二分(折半)插入法对一个无序数组R[1.n]进行排序。排序思想是对一个待插入元素，先通过二分法(折半)找到插入位置，后移元素后将该元素插入到恰当位置(假设R[]中的元素互不相同)。
【算法】
1．变量声明
X：DataType
i，j，low，high，mid，R[0..n])
2．每循环一次插入一个R[i]
循环：i以1为步长，从2到n，反复执行
①准备
X＜-R[i]； (1) ；high＜-i-1;
②找插入位置
循环：当 (2) 时，反复执行
(3) ;
若X.key＜R[mid].key
则high＜-mid-1
否则 (4)
③后移
循环：j以-1为步长，从 (5) ，反复执行
R[j+1]＜-R[j]
④插入
R[low]＜-X
3．算法结束