数组中的逆序对（归并排序）

/*
归并排序
A的逆序对 + B的逆序对 + A和B混合在一起的逆序对。
merge_sort_(vt, l, mid);求出逆序对的对数，并对他们排序
merge_sort_(vt, mid +1, r);
merge_(vt, l, mid, r);根据两个已经有序的块，求它们之间的逆序对。
*/

class Solution {
private: int kmod = 1000000007;
public:
    int InversePairs(vector<int> data) {
        return merge_sort_(data,0,data.size()-1)%kmod;
    }
    int merge_sort_(vector<int> &vt, int l, int r){
        if(l>=r)return 0;
        int mid = l + r >> 1;
        return merge_sort_(vt, l, mid) + 
        merge_sort_(vt, mid+1, r) + 
            merge_(vt, l, mid, r);
    }
    int merge_(vector<int> &vt,int l, int mid, int r){
        int res = 0;
        vector<int> tmp(r-l+1);
        int i = l, j = mid+1, k = 0;
        while(i<=mid && j<=r){
            if(vt[i] > vt[j]){
                res += mid-i+1;
                res %=kmod;
                tmp[k++] = vt[j++];
            }else{
                tmp[k++] = vt[i++];
            }
        }
       while(i <= mid)tmp[k++] = vt[i++];
       while(j <= r)tmp[k++] = vt[j++];
       for(i=l,k=0;i<=r;i++,k++) vt[i] = tmp[k];
       return res;
    }
};


class Solution {
private: int kmod = 1000000007;
public:
    int InversePairs(vector<int> data) {
         int ret  = 0; 
        merge_sort_(data, 0, data.size()-1, ret);
        return ret;
    }
    void merge_sort_(vector<int> &vt, int l, int r, int &ret){
        if(l >= r){return;}
        int mid = l + ((r-l) >> 1);
        merge_sort_(vt, l, mid, ret);
        merge_sort_(vt, mid +1, r, ret);
        merge_(vt, l, mid, r, ret);
    }

    void merge_(vector<int> &vt,int l, int mid, int r, int &ret){
        vector<int> tmp(r - l + 1);
        int i = l, j = mid + 1, k = 0;
        while(i <= mid && j <= r){
            if(vt[i]>vt[j]){
                tmp[k++] = vt[j++];
                ret += (mid - i + 1); 
// 区间内有序为了这一步，vt[i]>vt[j]则i以后元素也会大于vt[j]，构成逆序对,容易计算。
                ret %= kmod;
            }else{
                tmp[k++] = vt[i++];
            }
        }

        while(i <= mid){
            tmp[k++] = vt[i++];
        }
        while(j <= r){
            tmp[k++] = vt[j++];
        }
        for(k = 0, i = l; i <= r; ++i, ++k){
            vt[i] = tmp[k];
        }
    }
};