归并排序求逆序数

/*归并排序求逆序数*/
/*我们知道mergesort是稳定排序，所以就可以根据这个特点来求序列的逆序数
在Merge()中，合并两个已经有序的数组A,B.因为A.B有序,所以,A,B各自的逆序数是0,所以AB的逆序数等于A,B之间的逆序数.
*/
#include<iostream>
using namespace std;

typedef long long ll;
const ll N = 1e7+10;
ll a[N];
ll sum;
void merge(ll *A,ll start,ll mid, ll end)
{
    ll p = start,q = mid+1;
    ll arr[end-start+1],k=0;
    while(p<=mid&&q<=end)
    {
        if(a[p]<a[q])
        {
            arr[k++] = a[p++];
        }
        else
        {
            sum+=(mid-p+1);//求逆序数
            arr[k++] = a[q++];
        } 
    }
    while(p<=mid) arr[k++] = a[p++];
    while(q<=end) arr[k++] = a[q++];
    for(ll i =start;i<=end;++i)
        a[i] = arr[i-start];
}
void mergesort(ll *A,ll start,ll end)
{
    if(start<end)
    {
        //二分；分治
        ll mid = (start+end)>>1;
        mergesort(A,start,mid);
        mergesort(A,mid+1,end);
        merge(A,start,mid,end);
    }
}
int main()
{
    ll n;
    cout<<"please input the number of data"<<endl;
    while(cin>>n&&n)
    {
        sum = 0;
        cout<<"please input the sequence"<<endl;
        for(int i =0;i<n;++i)
            cin>>a[i];
        mergesort(a,0,n-1);
        cout<<"After sorting:"<<endl;
        for(int i =0;i<n;++i)
        {
            cout<<a[i]<<" ";
        }
        cout<<endl;
        cout<<"The number is"<<endl;
        cout<<sum<<endl;
        cout<<"please input the number of data"<<endl;
    }   
    system("pause");
    return 0;
}