2路归并排序 ：
introdution to algorithm 上讲解的不能再详细了， 我就不在这里班门弄斧了，贴一个带有部分注释的代码。
1 #include <stdio.h>
2 #include <string.h>
3 int a[100], left[100], right[100], nil = 0x7fffffff, n;
4 //left 为扣着的左边的牌 righg 为扣着的右半部分的牌。
5 // a 原地排序
6 void merge(int l, int r){
7
8 //printf("merge(%d %d)\n", l, r);
9 int i, j, p = (l + r) / 2, t;
10 for(i = l, t = 0; i <= p; i++, t++)left[t] = a[i];left[t] = nil; //初始化左边的牌
11 for(j = p + 1, i = 0; j <= r; j++, i++)right[i] = a[j];right[i] = nil; //初始化右边的牌
12 //printf("left : \n");
13 //for(i = 0; left[i] != nil; i++)printf("%d ", left[i]);
14 //puts("");
15 //puts("right : ");
16 //for(j = 0; right[j] != nil; j++)printf("%d ", right[j]);
17 //puts("");
18 for(p = l, i = j = 0; p <= r; p++){ // 对a进行原地排序，每次拿出一个左右边最小的一个放到里面。
19 if(left[i] < right[j])a[p] = left[i++];
20 else a[p] = right[j++];
21 }
22 }
23
24 void merge_sort(int l, int r){
25 int q;
26 if(l < r){ //对于这棵深度优先搜索树来说，merger 的调用，相当于后序遍历的， 也就是说，先两个儿子，然后根节点。
27 q = (l + r) / 2;
28 //printf("merger_sort(%d %d)\n", l, q);
29 merge_sort(l, q);
30 //printf("merger_sort(%d %d)\n", q + 1, r);
31 merge_sort(q + 1, r);//也就是合并 - -
32 merge(l, r);
33 }
34 }
35
36 int main(){
37 freopen("merge_sort.in", "r", stdin);
38 freopen("merge_sort.out", "w", stdout);
39 int i, j;
40 while(scanf("%d", &n) != -1){
41 for(i = 0; i < n; i++)
42 scanf("%d", &a[i]);
43 merge_sort(0, n - 1);
44 for(i = 0; i < n; i++)
45 printf("%d ", a[i]);
46 puts("");
47 }
48 return 0;
49 }
50