/*

题目：

	求给定数组的逆序对数。

*/

/*

思路：

	归并排序。

*/

#include<iostream>

#include<cstring>

#include<vector>

#include<algorithm>

#include<map>

using namespace std;

int merge(int A[], int left,int mid,int right){

   int myCount = 0;

   int p1 = left;

   int p2 = mid + 1;

   int temp[right-left+1];

   int i = 0;

   while(p1 <= mid && p2 <= right){

        if(A[p1] > A[p2]){

            myCount = myCount + 1 + mid - p1;//右边数字大于左边数字的个数。

            temp[i] = A[p2];

            p2++;

        }else{

            temp[i] = A[p1];

            p1++;

        }

        i++;

   }

   while(p1 <= mid){

        temp[i++] = A[p1++];

   }

   while(p2 <= right){

        temp[i++] = A[p2++];

   }

   for(int i = left; i <= right; i++){

        A[i] = temp[i-left];

   }

   return myCount;

}

int sort(int A[], int left,int right) {

    if(left == right){

       return 0;

    }

    int mid = left + ((right-left) / 2);

    //cout<<left<<" "<<mid<<" "<<right<<endl;

    int num1 = sort(A,left,mid);

    int num2 = sort(A,mid+1,right);

    return merge(A,left,mid,right) + num1 + num2;

}

int main(){

    int a[] = {1,3,7,2,4,1};

    cout<<sort(a,0,5)<<endl;

    for(int i = 0; i < 6;i++){

        cout<<a[i]<<" ";

    }

    return 0;

}