菜鸟天堂

template<typename T>
void insertion_sort( T * t, const int & size )
{
 int key,
  i, j,
  low, high, mid;
  
 for( i=1; i<size; i++ )
 {
  if( t[i] < t[i-1] )
  {
   low = 0;
   high = i-1;
   key = t[i];
   while( low <= high )
   {
    mid = (low+high)/2;
    
    if( key < t[mid] )
     high = mid - 1;
    else
     low = mid + 1;    
   }   
   for( j=i; j>high+1; j-- )
    t[j] = t[j-1];
   t[high+1] = key;
  }
 }
}

// 保持稳定性要求折半查找返回最后相等的关键字的位置或其右边
// high+1: 插入的位置

分析:
由于折半插入排序和直接插入排序相比, 仅减少了关键字比较的次数, 而记录移动次数不变. 其时间复杂度仍为O(n^2).  而且它查找和移动不是在同一个迭代中完成的. 所以只有当n较大时其性能才略优于直接插入排序.