折半插入排序的基本思想和直接插入排序类似，区别是查找插入位置的方法不同，折半插入排序是采用折半查找法来查找插入位置的。

折半查找法的一个基本条件是序列已经有序，而从直接插入排序的流程中可以看出，每次都是在一个已经有序的序列中插入一个新的关键字，因此可以用折半查找法在这个有序序列中查找插入位置。

1.执行流程

举一趟排序为例：

现在的序列是13 38 49 65 76 97 27 49

将要插入27，此时序列在数组中的情况为：

1）low=0，high=5，m=（0+5）/2=2，下标为2的关键字是49，27＜49，所以27应该插入到49的低半区，改变high=m-1=1，low仍然是0。

2）low=0，high=1，m=（0+1）/2=0，下标为0的关键字是13，27＞13，所以27应该插入到13的高半区，改变low=m+1=1，high仍然是1。

3）low=1，high=1，m=（1+1）/2=1，下标为1的关键字是38，27＜38，所以27应该插入到38的低半区，改变high=m-1=0，low仍然是1，此时low＞high，折半查找结束，27的插入位置在下标为high的关键字之后，即13之后。

4）依次向后移动关键字97，76，65，49，38，然后将27插入，这一趟折半插入排序结束。(www.daowen.com)

执行完这一趟排序的结果为：

13 27 38 49 65 76 97 49

2.性能分析

（1）时间复杂度分析

折半插入排序适合关键字数较多的场景，与直接插入排序相比，折半插入排序在查找插入位置上面所花的时间大大减少。折半插入排序在关键字移动次数方面和直接插入排序是一样的，所以其时间复杂度和直接插入排序还是一样的。

折半插入排序的关键字比较次数和初始序列无关。因为每趟排序折半查找插入位置时，折半次数是一定的（都是在low＞high时结束），折半一次就要比较一次，所以比较次数是一定的。

由此可知折半插入排序的时间复杂度最好情况为O（nlog₂n），最差情况为O（n²），平均情况为O（n²）。

（2）空间复杂度分析

空间复杂度同直接插入排序一样，为O（1）。