折半插入排序（Binary Insertion Sort）是對插入排序算法的一種改進。所謂插入排序，就是不斷的依次將元素插入前面已排好序的序列中。折半插入排序的基本思想跟直接插入排序基本一致，都是通過將元素一個個插入有序序列進行排序。兩者的區別在於尋找插入位置的方法，直接插入排序是由後往前一個個進行對比尋找合適的插入位置，而折半插入排序則是利用折半查找的思路尋找合適的插入位置。具體操作是，在將一個新元素插入已排好序的數組的過程中，尋找插入點時，採用折半查找的方法來加快尋找插入點的速度。由於折半插入排序減少了比較次數，所以速度比直接插入排序算法快，但記錄移動的次數沒有變，所以折半插入排序算法的時間複雜度仍然為O(n2)，與直接插入排序算法相同，附加空間O(1)。因此，折半插入排序是一種穩定的排序算法。