基本思想：将元素集合分成2个集合，对每个集合单独分类，然后将已分类的两个序列归并成一个含有n个元素的分类好的序列。这种思想是典型的分治法的设计思想。
归并排序
1 #include <iostream>
2 using namespace std;
3
4 //元素交换
5 void swap(int &a,int &b)
6 {
7 int temp=a;
8 a=b;
9 b=temp;
10 }
11
12 /*///////////////////////////////////////////////
13 归并排序
14 */
15 void Merge(int *a,int low,int mid,int high)
16 {
17 int b[100];
18 int l=low;
19 int h=mid+1;
20 int i=low;
21 int j;
22 while( l<=mid && h<=high ) //当分成的独立的两部分各自未超过范围时，比较元素，赋值给数组b中相应的元素
23 {
24 if(a[l]<=a[h])
25 b[i++]=a[l++];
26 else
27 b[i++]=a[h++];
28 }
29 if(l>mid) //当超出范围，判断是哪一部分先超出，然后将剩余部分直接添加到数组b中
30 for(j=h;j<=high;j++)
31 b[i++]=a[j];
32
33 if(h>high)
34 for(j=l;j<=mid;j++)
35 b[i++]=a[j];
36
37 for(j=low;j<=high;j++) //重写数组a中元素
38 a[j]=b[j];
39 }
40 void MergeSort(int *a,int low,int high) //递归，合并排序
41 {
42 if(low<high)
43 {
44 int mid=(low+high)/2;
45 MergeSort(a,low,mid);
46 MergeSort(a,mid+1,high);
47 Merge(a,low,mid,high);
48 }
49 }
50
51
52 /////////////////////////////////////////////////
53
54
55 int main()
56 {
57 int n,i,a[20];
58 cout<<"请输入数组元素n:"<<endl;
59 cin>>n;
60 cout<<"请输入"<<n<<"个元素:"<<endl;
61 for(i=0;i<n;i++)
62 cin>>a[i];
63 MergeSort(a,0,n-1);
64 for(i=0;i<n;i++)
65 cout<<a[i]<<" ";
66 cout<<endl;
67 return 0;
68 }