归并排序：
假设，每次排一段序列时就已经分别拥有了两段已经拍好顺序的子列，合并时每次只比较两子列的首项，并取出较小（大）的一项补在正在构建的新的目标序列尾部，重复这项操作，直至这一段序列排好顺序。
照此方法递归进行。
递归的每一层，每个数都会参与一次比较，一层内复杂度为 O（n）。
每次分为两段，复杂度 log2（n）。
总复杂度n*log2（n）。
int a[100005],b[100005];
void guibing(int l,int r)
{
if (l>=r) return ;
int mid=(l+r)/2;
guibing(l,mid);
guibing(mid+1,r);
for (int i=l,j=l,k=mid+1;i<=r;i++)//构建新数列
{
if (a[j]<=a[k] && j<=mid)
b[i]=a[j],j++;
else if (k<=r)
b[i]=a[k],k++;
else b[i]=a[j],j++;
}
for (int i=l;i<=r;i++)
a[i]=b[i];
return ;
}以及在归并排序中可以很轻松的实现求逆序对数量的操作。
#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;
int n,ans,a[100005],b[100005];
void guibing(int l,int r)
{
if (l>=r) return ;
int mid=(l+r)/2;
guibing(l,mid);
guibing(mid+1,r);
for (int i=l,j=l,k=mid+1;i<=r;i++)
{
if (a[j]<=a[k] && j<=mid)
b[i]=a[j],j++;
else if (k<=r)
b[i]=a[k],k++,ans+=mid-j+1;
else b[i]=a[j],j++;
}
for (int i=l;i<=r;i++)
a[i]=b[i];
return ;
}
int main()
{
scanf("%d",&n);
ans=0;
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
guibing(1,n);
printf("%d\n",ans);
}