数据结构老师讲了直接插入排序和折半插入排序。但是折半插入排序只是快速找到插入位置，对于数组来说，找到位置之后插入的话还是需要一位一位的挪，这挪的长度和直接插入排序没区别啊？而且折半插入排序还多了二分查找这个过程。理论上这两个时间复杂度应该一样吧，甚至折半插入排序应该还多了查找的时间。但是神奇的是直接插入排序就T了，折半插入排序就全A了，这是为什么呀？

#include <stdio.h>
#define N 100005

int n,a[N],b[N];

void prt()
{
	for(int i=1;i<=n;i++)
		printf("%d ",a[i]);
	puts("");
}

void insertsort()
{
	for(int i=2;i<=n;i++)
	{
		a[0]=a[i];//哨兵
		int j;
		for(j=i-1;a[j]>a[0];j--)//找最后一个小于等于a[i]的位置
			a[j+1]=a[j];
		a[j+1]=a[0];
	}
}

void binary_insertsort()
{
	for(int i=2;i<=n;i++)
	{
		int l=1,r=i,mid,pos=i;//l~r-1有序
		a[0]=a[i];
		while(l<r)//找第第一个大于a[i]的位置pos
		{
			mid=l+r>>1;
			if(a[mid]>a[0])
				r=pos=mid;
			else
				l=mid+1;
		}
		for(int j=i-1;j>=pos;j--)
			a[j+1]=a[j];//找到位置之后一样要挪
		a[pos]=a[0];
		//printf("%d %d\n",i,pos);
		//prt();
	}
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	//mergesort(1,n);
	//insertsort();
	binary_insertsort();
	prt();
}