int InsertSort(MergeType *L, int data)
{
 int j;

 if (!L->len)
 {
  L->elem[++L->len] = data;
  return 0;
 }

 for (j = L->len-1; j >= 0; --j)
 {
  if (data < L->elem[j])
  {
   L->elem[j+1] = L->elem[j];/*數(shù)據(jù)后移*/
  }
  else
  {
   L->elem[j+1] = data;
   L->len++;
   break;
  }
 }
 return 0;
}

#define  LISTLEN 10 
 MergeType pList;
 MergeType pT; 

 pList.elem = (int*)malloc(sizeof(int)*LISTLEN);
 ScanfList(&pList);
 pList.len  = LISTLEN;
 pList.size = LISTLEN;
 

 pT.elem = (int*)malloc(sizeof(int)*LISTLEN); 
 pT.len = 0;
 pT.size = LISTLEN;
 memset(pT.elem, 0, LISTLEN*sizeof(int));

 for (int i = 0; i < LISTLEN; i++ )
 {
  InsertSort(&pT, pList.elem[i]);
 }

 PrintList(&pT);

 free(pList.elem);
 free(pT.elem);
 pList.elem = NULL;
 pT.elem = NULL;

int InsertSort(MergeType* L)
{
 int i, j = 0;
 int nCompKey;

 if (!L->elem || !L->len) return -1;

 if (L->elem && (L->len==1)) return 0;

 for ( i = 1; i < L->len; i++) /*遞增的順序排列*/
 {
  if (L->elem[i] < L->elem[i-1])  /*第二個數(shù)據(jù)比第一個數(shù)據(jù)小*/
  {
   nCompKey = L->elem[i];
   L->elem[i] = L->elem[i-1];   

   //move elements back
   for (j = i-2; j >= 0 && nCompKey < L->elem[j]; --j) /*在>=退出當前循環(huán)*/
   {
    L->elem[j+1] = L->elem[j];
   }
   L->elem[j+1] = nCompKey;
  }
 }
 return 0;
}

 ...
 if (L->elem[i] < L->elem[i-1])  /*第二個數(shù)據(jù)比第一個數(shù)據(jù)小*/
 {
  nCompKey = L->elem[i];
  /*move elements back, compare count add once*/
  for (j = i-1; j >= 0 && L->elem[j] > nCompKey; --j) /*從較大的數(shù)往較小的數(shù)的方向*/
  {
   L->elem[j+1] = L->elem[j];
  }/*在>=退出當前循環(huán)*/
  L->elem[j+1] = nCompKey; /*此時val[j]<nCompKey，說明當前插入的位置應該在j之后*/
 }
 ...

/*折半插入排序算法*/
int BInsertSort(MergeType *L)
{
 int i, j;
 int low, high, mid;
 int nCompKey;

 for (i = 1; i <= L->len - 1; i++ )
 {
  nCompKey = L->elem[i];
  low = 0;
  high = i - 1;

  /*當low=high時，此時不能判斷插入的位置是在low=high的
   *前面還是后面，會進入下面的判斷*/
  while(low <= high)
  {
   mid = (low + high)/2;
   if ( nCompKey > L->elem[mid] )
   {
    low = mid + 1;/*當(low=mid+1)>high的時候，跳出循環(huán)*/
   }
   else
   {
    high = mid -1;/*當(high=mid-1)<low的時候，跳出循環(huán)*/
   }
  }/*low>high的時候，退出循環(huán)*/

  /*移動nCompKey之前的所有數(shù)據(jù)，這里使用high+1是因為high<low
   *的時候，按理數(shù)據(jù)應該放在high的位置，但是此時high的位置可
   *能已經(jīng)有排列好的數(shù)據(jù)或者不存在的位置,所以移動為后一個位置*/
  for (j = i-1; j >= high+1; j-- ) /*high是否可以使用low代替？？*/
  {
   L->elem[j+1] = L->elem[j];
  }
  /*當沒有元素的時候 high=-1*/
  L->elem[high+1] = nCompKey;
 }
 return 0;
}

#if 0
  for (j = i-1; j >= high+1; j-- ) /*high或許可以使用low代替*/
  {
   L->elem[j+1] = L->elem[j];
  }
  L->elem[high+1] = nCompKey;
#else
  for (j = i-1; j >= low; j-- ) /*使用low代替high+1*/
  {
   L->elem[j+1] = L->elem[j];
  }
  L->elem[low] = nCompKey;
#endif
...