歸并排序的含義就是將兩個或兩個以上的有序數據序列合并成一個新的有序數據序列。它的基本思想就是假設數組A有N個元素，那么可以看成數組A是又N個有序的子序列組成，每個子序列的長度為1，然后再兩兩合并，得到了一個 N/2 個長度為2或1的有序子序列，再兩兩合并，如此重復，值得得到一個長度為N的有序數據序列為止，這種排序方法也稱為2—路合并排序。
1
#include <stdio.h>
2#include <cstdlib>
3
4#define TOTAL_NUM 1000
5#define MAX_NUM 200
6
7int merge(int sort[],int iLit,int iMid,int iHig)
8
{
9
int n1 = iMid-iLit+1;
10 int n2 = iHig-iMid;
11 int *L = (int*)malloc((n1+2)*sizeof(int));
12 int *R = (int*)malloc((n2+2)*sizeof(int));
13
14 int i=0;
15 for (i=1;i<=n1;i++)
16
{
17 L[i] = sort[iLit+i-1];
18
}
19 int j=0;
20 for (j=1;j<=n2;j++)
21 {
22 R[j] = sort[iMid+j];
23 }
24 L[n1+1] = R[n2+1] = RAND_MAX;
25 i=j=1;
26 int k=0;
27 for (k=iLit;k<=iHig;k++)
28 {
29 if (L[i]<=R[j])
30 {
31 sort[k] = L[i];
32 i++;
33 }else
34 {
35 sort[k] = R[j];
36 j++;
37 }
38 }
39 free(L);
40 free(R);
41 return 0;
42
}
43
44void SORT(int sort[],int iLit,int iHig)
45{
46 int iMid = 0;
47 if (iLit<iHig)
48 {
49 iMid = (iLit+iHig)/2;
50 SORT(sort,iLit,iMid);
51 SORT(sort,iMid+1,iHig);
52 merge(sort,iLit,iMid,iHig);
53 }
54}
55
56int main(int argc,char* argv[])
57{
58 int Sort[TOTAL_NUM];
59
60 int iPrintCount = 0;
61 int i = 0;
62 printf("::: old order ::: \n");
63 for (i=0;i<TOTAL_NUM;i++)
64 {
65 Sort[i] = (rand()+MAX_NUM)%MAX_NUM;
66 printf("%5ld ",Sort[i]);
67 if(++iPrintCount==10)
68 {
69 iPrintCount = 0;
70 printf("\n");
71 }
72 }
73
74 //merge sort
75 SORT(Sort,0,TOTAL_NUM-1);
76
77 iPrintCount = 0;
78 printf("\n::: new order ::: \n");
79 for (i=0;i<TOTAL_NUM;i++)
80 {
81 printf("%5ld ",Sort[i]);
82 if(++iPrintCount==10)
83 {
84 iPrintCount = 0;
85 printf("\n");
86 }
87 }
88
89 getchar();
90 return 0;
91}