合并排序的关键步骤在于合并步骤中的合并两个已排序子序列。为做排序，引入一个辅助过程merger(A,p,q,r)，其中A是个数组，pqr是下标，
满足p<= q <
r。该过程假设A[p..q]和A[q+1..r]都已排序，并将它们合并成一个已经排好序的子数组代替当前子数组A[p..r]
1 #include<stdio.h>
2 #include<stdlib.h>
3 void merger(int * A,int p,int q,int r);
4 void mergerSort(int * A,int p,int r);
5 int main()
6 {
7 int A[10] = {0};
8 int i = 0;
9
10 for(i = 0;i < 10;i++)
11 {
12 scanf("%d",A + i);
13 }
14
15 printf("输入为：\n");
16 for(i = 0;i < 10;i++)
17 {
18
19 printf("%d",A[i]);
20 }
21 mergerSort(A,0,9);
22 printf("\n排序后:\n");
23 for(i = 0;i < 10;i++)
24 {
25 printf("%d",A[i]);
26 }
27 printf("\n");
28 return 0;
29 }
30 void merger(int * A,int p,int q,int r)
31 {
32 int n1 = q - p + 1;
33 int n2 = r - q ;
34 int i = 0,k = 0,j = 0;
35 int * L = (int*)malloc(sizeof(int) * n1 + 1);
36 int * R = (int *)malloc(sizeof(int) * n2 + 1);
37 for(i = 0;i < n1;i++)
38 {
39 L[i] = A[p + i];
40 }
41 L[i] = 99999;
42 for(i = 0;i < n2;i++)
43 {
44 R[i] = A[q + i + 1];
45 }
46 R[i] = 99999;
47 i = j = 0;
48
49 for(k = p;k <= r;k++)
50 {
51 if(L[i] < R[j])
52 {
53 A[k] = L[i];
54 i++;
55 }
56 else
57 {
58 A[k] = R[j];
59 j++;
60 }
61 }
62 free(R);
63 free(L);
64 }
65 void mergerSort(int * A,int p,int r)
66 {
67 int mid = 0;
68 if(p < r)
69 {
70 mid = (r + p) / 2;
71 mergerSort(A,p,mid);
72 mergerSort(A,mid + 1,r);
73 merger(A,p,mid,r);
74 }
75 }
运行结果：
chu@szcdebian:~/code/merge-sort$ gcc -o merge merge-sort.c
chu@szcdebian:~/code/merge-sort$ ./merge
9 0 6 8 7 3 4 2 5 1
输入为：
9068734251
排序后:
0123456789
chu@szcdebian:~/code/merge-sort$