折半插入排序的思想就是折半查找和插入排序结合起来。首先将待排序元素放入a[0]，之后运用插入排序找到该元素的插入位置，定义一个low ,high，取中间元素，之后比较a[0],和a[mid]的大小，如果比mid小则就让high = mid-1否则就让low = mid +1,直到循环结束high<low,让high+1，i-1的元素后移动，让a[high+1] = a[0]结束。

#include<stdio.h>
int main(){
    int low,high,mid;
    int a[100];
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=2;i<=n;i++){
        a[0] = a[i];
        low = 1;
        high = i-1;
        while(low<=high){
            mid = (low+high)/2;
            if(a[0]  < a[mid]){
                high = mid -1;
            }
            else {
                low = mid+1;
            }
        }
            for(int j=i-1;j>=high+1;j-- )
                a[j+1] = a[j];
            a[high+1] =a[0];
         
    }
    for(int i=1;i<=n;i++){
        printf("%d ",a[i]);
    }
}

折半插入排序的时间复杂度为o($$n^2$$)该算法稳定。