归并排序

归并排序，是将区间分为两部分，先对小的区间进行排序，然后再合并到大的区间中，最后实现全部排好序。

#include<bits/stdc++.h>
using namespace std;
int a[100010],temp[100010];
void merge(int L,int R){  //对区间进行划分成前两半和后两半
    int mid=(L+R)>>1;
    int k=1,l=L,r=mid+1;
    while(l<=mid&&r<=R){
        if(a[l]<=a[r])  temp[k++]=a[l++];
        else{
            //这里可以用来求逆序对 sum+=(mid-l+1) 
            temp[k++]=a[r++];
        }
    }
    while(l<=mid) temp[k++]=a[l++];
    while(r<=R) temp[k++]=a[r++];
    for(int i=L,k=1;i<=R;i++,k++){
        a[i]=temp[k];
    }
}
void mergesort(int l,int r){
    if(l<r){   //注意这里的条件
        int mid=(l+r)>>1;
        mergesort(l,mid);
        mergesort(mid+1,r);
        merge(l,r);
    }
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)  cin>>a[i];
    mergesort(0,n-1);
    for(int i=0;i<n;i++)  cout<<a[i]<<" ";
    cout<<endl;
    return 0;
}