归并排序的含义就是将两个或两个以上的有序数据序列合并成一个新的有序数据序列。它的基本思想就是假设数组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}