归并排序求解数组中的逆序对

简单分析：因为归并排序会不断把一个数组分成两个数组[L,mid], [mid+1, r]，然后再递归一层一层排序，合并两个子数组，根据这个性质可以发现：

1. 我们可以将逆序对分为三大类，以归并排序的mid分割开来。
2. 第一大类为[l,mid]区间的，第二大类为[mid+1，r]之间的。第三类为一个在左区间，一个在右区间。
3. 前两类的结果则为ll res = merge_sort(l, mid) + merge_sort(mid + 1, r);而第三类的结果则可以在归并数组两个数组的过程中找到。令q[i]为左边，q[j]为右边。我们发现若q[i] > q[j]，则左边 q[i]……q[mid]都大于q[j] (因为归并排序是先排序好左右两个区间才开始合并的)，所以结果则为 res += mid - i + 1;
4. 得出如下代码

class Solution {
private:
    const static  int N = 100010;
    int q[N], t[N];
    using ll = long long;
public:
    //归并排序，结果可能会爆int,所以要long long
    ll merge_sort(int l, int r) {
    
    if (l >= r) return 0;//递归终止条件
    
    int mid = (l + r) >> 1;//取中间，分成两个区间
    
    ll res = merge_sort(l, mid) + merge_sort(mid + 1, r);//前两类区间的结果
      
    //第三类区间的结果
    int i = l, j = mid + 1;
    int k = 0;
    while (i <= mid && j <= r) {
        if (q[i] <= q[j]) t[k++] = q[i++];
        
        else {
            
            t[k++] = q[j++];
            
            res += mid - i + 1;//获取结果
        }
    }
      //扫尾操作
    while (i <= mid) {
      
        t[k++] = q[i++];
        //++result;
    }
    
    while (j <= r) t[k++] = q[j++];
    //回到上一层前，要将排序结果赋给原始数组
    for (int i = l, j = 0; i <= r; ++i, ++j) q[i] = t[j];
    
    return res;

    }
    
    int InversePairs(vector<int> data) {
        
        for (int i = 0; i < data.size(); ++i) q[i] = data[i];

        ll res = merge_sort(0, data.size() - 1);

        return res % 1000000007;
    }
};