由于插入排序的基本思想是在一个有序序列中插入一个新的记录，则可以利用"折半查找"查询插入位置，由此得到的插入排序算法为"折半插入排序"。算法如下：
算法 10.3void BInsertSort (SqList &L)
{
// 对顺序表L作折半插入排序
for ( i=2; i<=L.length; ++i )
{
L.r[0] = L.r[i]; // 将L.r[i]暂存到L.r[0]
low = 1; high = i-1;
while (low<=high)
{ // 在r[low..high]中折半查找有序插入的位置
m = (low+high)/2; // 折半
if (L.r[0].key < L.r[m].key)) high = m-1; // 插入点在低半区
else low = m+1; // 插入点在高半区
} // while
for ( j=i-1; j>=low; --j ) L.r[j+1] = L.r[j]; // 记录后移
L.r[high+1] = L.r[0]; // 插入
}
} // BInsertSort
但是，折半插入排序只能减少排序过程中关键字比较的时间，并不能减少记录移动的时间，因此折半插入排序的时间复杂度仍为O (n2)。
从上一节的讨论可知，直接插入排序的算法简单易行，但由于它的时间复杂度为O (n2)，因此对长度很大的记录序列宜采用性能更好的插入排序算法。
从动画演示可见，折半插入排序过程中的折半查找的目的是查询插入点，因此不论是否存在和给定值相同的关键字，结束查找过程的条件都是high<low，并且插入位置为low指示的地方。"折半插入"不失为是一条减少关键字比较次数的途径，它是"归并插入排序"（可使排序过程中的关键字比较次数达到最少的一种排序方法）的基本依据。