归并排序 （模板）

分治的思想，时间复杂度O(nlogn)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>

using namespace std;
const int MAXN = 100005;

inline int rd(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0' && ch<='9')  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}

int n,a[MAXN],cpy[MAXN];

inline void merge_sort(int l,int r){
    if(l==r) return;
    int mid=l+r>>1;
    merge_sort(l,mid);
    merge_sort(mid+1,r);
    int i=l,j=mid+1,k=l;
    while(i<=mid && j<=r){
        if(a[i]<=a[j]) cpy[k++]=a[i++];
        else cpy[k++]=a[j++];
    }
    for(i;i<=mid;i++) cpy[k++]=a[i];
    for(j;j<=r;j++)   cpy[k++]=a[j];
    for(register int i=l;i<=r;i++) a[i]=cpy[i];
}

int main(){
    n=rd();
    for(register int i=1;i<=n;i++) a[i]=rd();
    merge_sort(1,n);
    for(register int i=1;i<=n;i++) printf("%d ",a[i]);
    return 0;
}