归并排序(分治)

归并排序，模型如下:
if low<high
then mid<-[n/2]
call mergesort(low,mid);
call mergesort(mid+1,high);
call merge(low,mid,high);
endif
end mergesort

示例程序:
[cpp]

#include <iostream>
using namespace std;
long long cnt;
int a[1000010];
void merge(int s1,int e1,int s2,int e2)
{
int p1=s1,p2=s2,p=0,*t;
t=new int[e2-s1+5];
while(p1<=e1&&p2<=e2)
{
if(a[p1]<=a[p2]) t[p++]=a[p1++];
else {t[p++]=a[p2++];cnt+=e1-p1+1;}
}
while(p1<=e1) t[p++]=a[p1++];
while(p2<=e2) t[p++]=a[p2++];
int i;
for(i=s1;i<=e2;i++) a[i]=t[i-s1];
delete t;
}
void mergesort(int s,int e)
{
int m;
if(s<e)
{
m=(s+e)/2;
mergesort(s,m);
mergesort(m+1,e);
merge(s,m,m+1,e);
}
}
int main()
{
int t,n,i;cin>>t;
while(t–)
{
cin>>n;cnt=0;
for(i=0;i<n;i++) cin>>a[i];
mergesort(0,n-1);
cout<<cnt<<endl;
}
return 0;
}

[/cpp]