可以说二路插入排序是对折半插入排序的进一步改进，目的就是为了减少折半插入排序记录移动的次数， 但是二路插入排序需要借助n个记录的辅助空间，也就是说他的空间复杂度为O(n);
初始关键字序列 51 33 62 96 87 17 28 51i=1 [51] first finali=2 [51] [33] final firsti=3 [51 62] [33] final firsti=4 [51 62 96] [33] final firsti=5 [51 62 87 96] [33] final firsti=6 [51 62 87 96] [17 33] final firsti=7 [51 62 87 96] [17 28 33] final firsti=8 [51 51 62 87 96] [17 28 33] final first
算法描述
void BiInsertSort(RecType R[],int n)
{
int d[n+1];
d[1] = R[1];first = 1; final= 1;
for(i=2;i<=n;i++)
{
if(R[i[.key >= d[1].key)
{
low =1 ;high = final;
while(low<=high) //折半查找
{
m = (low+high)/2;
if(R[i[.key < d[m].key) high = m+1;
else low = m+1;
}
for(j=final;j>=high+1;j--)//移动元素
{
d[j+1] = d[j];
d[high+1] = R[i];
final++;
}
else
{
if(first == 1)
{
first=n;
d[n] = R[i];
}
else
{
low = first;high=n;
while(low <= high)
{
m = (low+high)/2;
if(R[i].key < d[m].key) high = m-1;
else low=m+1;
}
for(j=first;j<=high;j++)
{
d[j-1] = d[j];
}
d[high] = R[i];
first--;
}
}
//将序列复制回去
R[1] = d[first];
for(i=first%n +1,j=2; i!= first; i = i%n,j++)
R[j] = d[i];
}
在二路插入排序中，移动记录的次数约为n2/8;因此二路插入排序并不能绝对的避免记录移动，并且当记录R[1]的关键字是最小或者最大是，二路插入排序的优越性也就没有了。
