归并排序可以理解为快排的反向，采用分治的思想，先排两边在用O(n)的时间合并在一起
代码（感觉比快排实现容易些） 
#include<bits/stdc++.h>
using namespace std;
void merge(int a[],int l,int r){
    int b[r-l+1],mid=(l+r)>>1,l1=0,r1=mid+1-l;
    for(int i=l;i<=r;i++) b[i-l]=a[i];
    for(int i=l;i<=r;i++){
        if(r1+l>r) a[i]=b[l1++];
        else if(l1+l>mid) a[i]=b[r1++];
        else if(b[l1]>b[r1]) a[i]=b[r1++];
        else a[i]=b[l1++];
    }
}
void merge_sort(int a[],int l,int r){
    if(l>=r) return ;
    int mid=(l+r)>>1;
    merge_sort(a,mid+1,r);
    merge_sort(a,l,mid);
    merge(a,l,r);
}
int main(){
    int n;
    int a[19993];
    srand(time(0));
    n=rand()%1000+1;
    for(int i=0;i<n;i++)a[i]=rand()%100+1;
    merge_sort(a,0,n-1);
    for(int i=0;i<n;i++)cout<<a[i]<<endl;
}