#include <stdio.h>

 #include <stdlib.h>

 #define EQ(a, b) ((a) == (b))    //数a和数b相等则为True,否则为False

 #define LT(a, b) ((a) <  (b))    //数a小于数b则为True

 #define LQ(a, b) ((a) <= (b))    //数a小于或等于数b则为True

 #define MAXSIZE 20    //待排序数的最多个数

 typedef int KeyType;    //定义待排序数据的关键字类型为int

 typedef int InfoType;    //定义待排序数据的其他信息类型为int

 typedef struct{

     KeyType key;        //关键字

     InfoType otherinfo;    //其他数据项

 }RedType;    //记录类型

 typedef struct{

     RedType r[MAXSIZE+];    //r[0]闲置或用作哨兵单元

     int length;    //顺序表长度

 }SqList;    //顺序表类型

 /*

  * 顺序打印序列表L中的关键字

  */

 void PrintList(SqList L){

     int i = ;

     printf("len:%d; data:", L.length);

     for(i=; i<=L.length; i++){

         printf("%d ", L.r[i].key);

     }

     printf("\n");

     return ;

 }

 #define DEBUG 

 /*

  * 2-路插入排序算法的实现

  *

  * @param

  *        SqList *L : 待排序的顺序表

  */

 void TwoInsertSort(SqList *L)

 {

     //数组D是和L中关键字列表长度相同的辅助数组

     RedType D[MAXSIZE] = {};

     //将L中第一个数据存入D[0]

     D[] = L->r[];

     int i = , j = , n = L->length;

     //first表示D中最小值下标，final表示D中最大值下标

     int first = , final = ;

     int k = ;

 #ifdef DEBUG

     for(j=; j<n; j++){

         printf("%d  ", D[j].key);

     }

     printf("\nthe %d lap:fist=%d, final=%d\n\n", i, first, final);

 #endif

     for(i=; i<=L->length; i++){

         if(LT(L->r[i].key, D[first].key)){

             // 待插入元素比最小的元素小

             first = (first-+n)%n;

             D[first] = L->r[i];

         }else if(LT(D[].key, L->r[i].key)){

             // 待插入元素比最大的元素大

             final = (final+)%n;

             D[final] = L->r[i];

         }else{

             // 待插入元素处在最小元素和最大元素中间

             // 采用直接插入排序的方法，插入到数组D中合适的位置

             k = (final+)%n;

             while(LT(L->r[i].key, D[(k-+n)%n].key)){

                 D[(k+n)%n] = D[(k-+n)%n];

                 k = (k-+n)%n;

             }

             D[(k+n)%n] = L->r[i];

             final = (final+)%n;

         }

 #ifdef DEBUG

         for(j=; j<n; j++){

             printf("%d  ", D[j].key);

         }

         printf("\nthe %d lap:fist=%d, final=%d\n\n", i, first, final);

 #endif

     }

     //将排序记录复制到原来的顺序表里

     for(j=; j<n; j++){

         L->r[+j] = D[first];

         first = (first+)%n;

     }

 }

 int  main(int argc, char *argv[])

 {

     if(argc < ){

         return -;

     }

     SqList L;

     int i = ;

     for(i=; i<argc; i++){

         if(i>MAXSIZE)

             break;

         L.r[i].key = atoi(argv[i]);

     }

     L.length = (i-);

     TwoInsertSort(&L);

     PrintList(L);

     return ;

 }