POJ 2299 Ultra-QuickSort

[merge sort]

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<cstring>
#include<vector>
#define min(x,y) (((x)>(y)) ? (y):(x))
#define max(x,y) (((x)>(y)) ? (x):(y))
using namespace std;
#define N 500000
#define LL long long int
LL line[N];
LL pp[N];
int n;
LL merge(int a,int b)
{
if(b==a) return 0 ;
if(b==a+1)
{
if(line[a]>line[a+1])
{
line[a]^=line[a+1]^=line[a]^=line[a+1];
return 1;
}
return 0;
}
int mid=(a+b)>>1;
LL res=0;
res+=merge(a,mid);
res+=merge(mid+1,b);
int ptr1=a;
int ptr2=mid+1;
for(int lx=a;lx<=b;lx++)
{
if(ptr1==mid+1)
pp[lx]=line[ptr2++];
else if(ptr2==b+1)
{
pp[lx]=line[ptr1++];
res+=(LL)(b-mid);
}
else
{
if(line[ptr1]>line[ptr2])
pp[lx]=line[ptr2++];
else
{
pp[lx]=line[ptr1++];
res+=(LL)(ptr2-1-mid);
}

}
}
for(int lx=a;lx<=b;lx++)
line[lx]=pp[lx];
return res;
}
int main()
{
while(scanf("%d",&n)&&n)
{
for(int lx=0;lx<n;lx++)
scanf("%I64d",line+lx);
printf("%I64d\n",merge(0,n-1));
}
return 0;
}