归并排序

就是单纯的归并排序(#^.^#)

#include<bits/stdc++.h>
#define fi first
#define se second
#define INF 0x3f3f3f3f
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pqueue priority_queue
#define NEW(a,b) memset(a,b,sizeof(a))
#define lowbit(x) ((x)&(-x))
using namespace std;
const double pi=4.0*atan(1.0);
const double e=exp(1.0);
const int maxn=1e5+8;
typedef long long LL;
typedef unsigned long long ULL;
const LL mod=1e9+7;
const ULL base=1e7+7;
void Merge_sort(LL arr[],int l,int r){
    if(l>=r)return ;
    int mid=(l+r)>>1;
    Merge_sort(arr,l,mid);
    Merge_sort(arr,mid+1,r);
    LL Le[maxn],Ri[maxn];
    int ls=mid-l,rs=r-mid-1,lt=0,rt=0,t=l;
    for(int i=l;i<=mid;i++){
        Le[i-l]=arr[i];
    }
    for(int i=mid+1;i<=r;i++){
        Ri[i-mid-1]=arr[i];
    }
    while(lt<=ls&&rt<=rs){
        if(Le[lt]<Ri[rt]){
            arr[t++]=Le[lt++];
        }
        else{
            arr[t++]=Ri[rt++];
        }
    }
    while(lt<=ls){
        arr[t++]=Le[lt++];
    }
    while(rt<=rs){
        arr[t++]=Ri[rt++];
    }
}
LL a[maxn];
int main(){
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    Merge_sort(a,1,n);
    for(int i=1;i<=n;i++){
        if(i!=1){
            cout<<' ';
        }
        cout<<a[i];
    }
    system("pause");
    return 0;
}