归并排序是经典的排序算法之一，是分治思想的体现。虽然在排序大多用sort就能搞定，但是有些题用可以用归并顺带就解决掉了(比如求逆序对)。

归并排序大概就是先将整个序列分为足够小的片段，然后在每个小片段里面进行排序，然后再依次合并，排序。过程如下图 (图源@努力的老周) 。

接下来用洛谷里一道求逆序对的题来用代码进行展示：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5+5;
int a[N],b[N];
int n,x;
int ans;
void merge_pai(int l, int mid, int r)
{int i=l, j=mid, k=l;while(i<mid&&j<=r){if(a[i]<=a[j])//小的那个先合进去b[k++]=a[i++];else{b[k++]=a[j++];ans+=mid-i;//此时加上前面所有大于的就是逆序对的数量}}while(i<mid) b[k++]=a[i++];//把前半部分剩余的给加上while(j<=r) b[k++]=a[j++];//加上后半部分剩余的for(int i=l; i<=r; i++)a[i]=b[i];
}
void merge_sort(int l, int r)
{if(l>=r) return ;int mid=(l+r)/2;merge_sort(l,mid);//将序列分为前半部分merge_sort(mid+1,r);//和后半部分merge_pai(l,mid+1,r);//将此时序列进行排序
}
void solve()
{cin >> n;for(int i=1; i<=n; i++) cin >> a[i];merge_sort(1,n);//开始分cout << ans;
}
signed main()
{ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);int t=1;
//	cin >> t;while(t--) solve();
}