#include <stdio.h>
#include <stdlib.h>
#define MAXLEN100
int a[MAXLEN];//用于存放目标序列
void merg(int a[] , int b[] , size_t left , size_t mid , size_t right) {//merg（合并）
//将a中下标从left到mid(middle)和从mid + 1到right的两个子序列进行合并
//前提是该两个子序列都已经排好序
//最后将合并好的序列存入b中的相应位置
size_t i , j , k;
for ( i = left , j = mid + 1 , k = left ;
i <= mid && j <= right ;
k++ ) {//从两个子序列的头部开始逐个比较，将较小的元素逐个存入b中
if ( a[i] < a[j] )
b[k] = a[i++];
else
b[k] = a[j++];
}
//将a或b中多余的元素直接插到b的最后
while ( i <= mid )
b[k++] = a[i++];
while ( j <= right )
b[k++] = a[j++];
}
void mpass(int a[] , int b[] , size_t len , size_t size) {//merge pass
//从左到右按照指定宽度size将a合并，并存入b中
size_t i = 0;
while ( len - i >= size + size ) {
merg(a , b , i , i + size - 1 , i + size + size - 1);
i += size + size;//每次让i移动两倍宽度
}
if ( len - i > size )//如果剩余序列的长度大于一倍size，则将前size部分和后面不足size的部分合并
merg(a , b , i , i + size - 1 , len - 1);
else//如果剩余序列长度不足size，则直接插入到b的最后
while ( i < len )
b[i++] = a[i];
}
void msort(int a[] , int b[] , size_t len) {//merge sort（合并排序）
//借助b的临时空间对a进行合并排序，最后结果是存在a中的！！！
size_t size = 1;
while ( size < len ) {
mpass(a , b , len , size);//先将a倒入b
size += size;
mpass(b , a , len , size);//再将b倒入a，以保证最终结果是存在a中的
size += size;
}//利用b在a、b之间来回倒要比每次在merg中malloc临时空间直接将排好的结果存放在a中快n倍，频繁malloc将导致频繁访问内核（速度是非常慢的！！）
}
int main() {
int *b = malloc( MAXLEN * sizeof(int) );//如果a过大，再用栈分配临时空间可能会导致栈崩，因此使用堆中的空间
//为了避免多再次在merg中malloc，因此直接在main中一次性malloc足够的空间
if ( !b )
exit(EXIT_SUCCESS);
size_t len;
scanf("%u" , &len);
int i;
for ( i = 0 ; i < len ; i++ )
scanf("%d" , a + i);
msort(a , b , len);
free(b);
for ( i = 0 ; i < len ; i++ )
printf("%d " , a[i]);
putchar('\n');
return 0;
}
测试数据（两组，执行两次）：
5 input
5 4 3 2 1
1 2 3 4 5 output
7 input
3 45 12 34 5 44 8
3 6 8 12 34 44 45 output