归并排序（Merge Sort）

参考资料

• 归并排序 - OI Wiki
• 归并排序 - 维基百科

实现

#include <bits/stdc++.h>
#define mid (l+r>>1)
using namespace std;

using ll=long long;
const int N=500005;
int a[N],b[N];
void msort(int l,int r)
{
	if(l==r)return;
	msort(l,mid);
	msort(mid+1,r);
	int p1=l,p2=mid+1;
	for(int i=l;i<=r;i++)
	{
		if(p1<=mid&&(p2>r||a[p1]<=a[p2]))
		{
			b[i]=a[p1++];
		}
		else
		{
			b[i]=a[p2++];
		}
	}
	for(int i=l;i<=r;i++)a[i]=b[i];
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	msort(1,n);
	for(int i=1;i<=n;i++)
	{
		cout<<a[i]<<' ';
	}
	return 0;
}

例题

洛谷 P1908 逆序对

洛谷 P1908 逆序对

给定一个长度为 $n$ 的正整数序列 $a_i$，求逆序对数量。（$n\le5\times10^5$）

逆序对：满足 $a_i>a_j$ 且 $i<j$ 的有序对 $(i,j)$。

#include <bits/stdc++.h>
#define mid (l+r>>1)
using namespace std;

using ll=long long;
const int N=500005;
int a[N],b[N];
ll ans=0;
void msort(int l,int r)
{
	if(l==r)return;
	msort(l,mid);
	msort(mid+1,r);
	int p1=l,p2=mid+1;
	for(int i=l;i<=r;i++)
	{
		if(p1<=mid&&(p2>r||a[p1]<=a[p2]))
		{
			b[i]=a[p1++];
		}
		else
		{
			b[i]=a[p2++];
			ans+=mid-p1+1;
		}
	}
	for(int i=l;i<=r;i++)a[i]=b[i];
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	msort(1,n);
	cout<<ans<<'\n';
	return 0;
}