归并排序算法

归并排序的思想就是：二分法

 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