2-路插入排序，不要说网上有，网上大多是错的，或不是2-路插入排序,该如何解决

2-路插入排序，不要说网上有，网上大多是错的，或不是2-路插入排序
书上说2-路插入排序是在折半插入排序上的再改进。

可我在网上查了好久，发现大家的代码和折半插入排序没什么关系，那怎么叫做在折半插入排序上的改进呢？
void BidirSort(int a[],int tem[],size_t size)
{
   
  int i,j;
  tem[0]=a[0];
  int first,final;
  first=final=0;
  for(i=1;i<size;i++)
  {
  if(a[i]>=tem[final])
  {
  tem[++final]=a[i];
  }
  else if(a[i]<=tem[first])
  {
  first=(first-1+size)%size;
  tem[first]=a[i];
  }
  else //下面是直接插入排序，根本不是折半插入
  {
  j=final;
final++;
  for(;a[i]<tem[j];j=(j-1+size)%size)
{
tem[(j+1)%size]=tem[j];
}
tem[(j+1)%size]=a[i]; //有人写成tem[j+1]=a[i]有错误，j==size怎么办？

  }
}
for(j=0;j<size;j++,first=(first+1)%size)
a[j]=tem[first];

}
我理解的是当要插入的数小于final 大于first时用折半插入排序，不过该怎么取中间值?明显不是（final+first）/2

[解决办法]
以前总结的。。。

Java code

    public void sort(int[] array) {        if (array == null) {            System.out.println("array is null .");            return;        }        for (int i = 1; i < array.length; i++) {            int key = array[i];            int left = 0;            int right = i - 1;            int j = 0;            if (key >= array[right]) {                continue;            } else if (key <= array[left]) {            } else {                while (right-left>1) {                        j = (left + right) / 2;                    if (key == array[j]) {                        break;                    } else if (key < array[j]) {                                                right = j;                                        } else {                        left = j;                    }                }                j = right-left<=1?right:j;            }            for (int m = i; m > j; m--) {                array[m] = array[m - 1];            }            array[j] = key;        }    }