数组中的逆序对

class Solution {
private:
    long int cnt = 0; //用于记录逆序对的个数,这里要定义long int    int可能会溢出
public:
    void merge(vector<int> &arr, int left, int mid, int right)
    {
        vector<int> temp(right-left+1);
        int i = left, j = mid + 1, k = 0;
        while(i<=mid && j<=right)
        {
            if(arr[i] <= arr[j])
            {
               temp[k++] =  arr[i++];
            }
            else
            {
                temp[k++] =  arr[j++];
                cnt = (cnt + mid - i + 1); // 由于左边arr[i]大于右边的arr[j],且是升序的，所以i---mid之间的数都大于arr[j]
            }
        }
        // 下面是将上面左右两边没有比完的数据进行分配
        while(i<=mid)
        {
           temp[k++] = arr[i++]; 
        }
        while(j<=right)
        {
            temp[k++] = arr[j++];
        }
        for(int m=0; m<right-left+1; m++)
        {
            arr[left + m] = temp[m];
        }
    }
    void mergeSort(vector<int> &arr, int left, int right)
    {
        // 递归条件
        if(left >= right)
        {
            return;
        }
        int mid = (left+right)/2; 
        mergeSort(arr, left, mid);
        mergeSort(arr, mid+1, right);
        merge(arr, left, mid, right);
    }
    int InversePairs(vector<int> data)
    {
        if(data.size()<=1) return 0;//如果少于等于1个元素，直接返回0
        mergeSort(data, 0, data.size()-1);
        return cnt%1000000007;
    }
};