折半插入排序是对直接插入排序的优化。假如我们需要尝试找到第 i 个元素插入的位置，直接插入排序是从右向左进行遍历一个个去找。瓶颈就出现在这里。

由于我们的插入排序是从左到右进行遍历的，所以当我们遍历到第 i 个元素的时候前 i - 1 个元素已经有序了，于是我们就可以用二分查找找到待插入的位置。进行插入。

由于我们只对找到插入位置进行了优化，并没有对元素后移进行优化，所以算法的时间复杂度并没有变化，还是 ${\displaystyle O(n^2)}$。

实现

以下是升序的实现：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;
int n;
int a[N];

void insert_sort() {
    for (int i = 1; i < n; i++) {
        if (a[i - 1] <= a[i]) continue;
        int t = a[i];
        int l = 0, r = i - 1;
        // 找到比 a[i] 大的第一个数
        while (l < r) {
            int mid = l + r >> 1;
            if (a[mid] > t) r = mid;
            else l = mid + 1;
        }
        // 移位
        for (int j = i - 1; j >= l; j--) 
            a[j + 1] = a[j];
        // 插入
        a[l] = t;
    }
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    
    insert_sort();
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    return 0;
}