歸并排序是經典的排序算法之一，是分治思想的體現。雖然在排序大多用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();
}