参考：[http://www.crazycoder.cn/]基本的思路是先从list中依次找出两个有序的子list,merge之，再继续找．scan一轮后，进行下一轮的查找，直到发现从list首到list尾为最大的有序子列(即list有序)为止．

参考：[http://www.crazycoder.cn/]额外的空间开销大，但是充分利用了list中的有序部分，减少了扫描次数．

参考：[http://www.crazycoder.cn/]ＢＴＷ：据说这样的方法适合于并行计算．:)

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

#define MAX_LENGTH 100

/*Show usage*/
void usage(char * prog)
{
printf(\"%s Usage:\\n\", prog);
printf(\"%s <length of the list>(should be less than 100)>\\n\", prog);
}

/*Generate and initialize the list*/
int * generate_list(int count)
{
int i;
int * list;

list = (int *)malloc(count*sizeof(int));
if(list == NULL)
{
perror(\"malloc\");
return NULL;
}

/*Initialize the list with integers less than 100*/
srandom((unsigned int)time(NULL));
for (i = 0; i < count ; i ++)
list[i] = random()%100;

return list;
}

/*Show the list*/
void show_list(int * list, int length)
{
int i;
for(i = 0; i < length; i ++)
printf(\"%d \", list[i]);

printf(\"\\n\");
}

void merge(int * srclist, int first, int mid, int last)
{
int * ord_list = (int *)malloc((last - first + 1)* sizeof(int));
int i = first, j = mid+1, k = 0;
int t;
while((i <= mid) && (j <= last))
{
if(srclist[i] < srclist[j])
{
ord_list[k] = srclist[i];
i ++;
k ++;
}
else
{
ord_list[k] = srclist[j];
j ++;
k ++;
}
}

if(i > mid)
{
for(t = j; t <= last; t ++)
{
ord_list[k] = srclist[t];
k ++;
}