归并排序的思想就是:二分法
1 void Merge(int A[],int l,int m,int r){
2 int i=l, j=m+1, k=1;
3 int b[N];
4 while(i<=m && j<=r){
5 if(A[i]<=A[j])b[k++]=A[i++];
6 else b[k++]=A[j++];
7 }
8 while(i <= m) b[k++] = A[i++];
9 while(j <= r) b[k++] = A[j++];
10 for(int i=1;i<k;++i)A[l+i-1]=b[i];
11 }
12 void MergeSort(int A[], int p, int r){
13 if(p<r){
14 int q=(p+r)/2;
15 int b[N];
16 MergeSort(A,p,q);
17 MergeSort(A,q+1,r);
18 Merge(A,p,q,r);
19 }
20 }
调用:
MergeSort(a,0,n-1); //数组为a[],长度为n