归并排序得结果

问题转化：求逆序对就是统计有多少个前大后小的数对，问题和归并两个有序数组求前大后小数对一样。所以现在的问题变为统计子问题中逆序对的个数。

递归模型变形：递归按照标准的归并排序来，注意的是统计个数，当出现nums[i]>nums[j]时，统计所有前半段区间内比nums[j]大的数及为ans+=m-i+1;（为了理解方便l~m前半段，m+1~r后半段）

边界注意：

1. i == r+1当前半段已经统计完，剩下后半段归并，证明j后的数都是比nums[m]大的，无需统计
2. j == l+1当后半段统计完，剩下前半段归并，i后的数都比num[l]大，但在之前已经统计个数，无需统计

public class Solution {
    
    int[] nums,temp;
  
    public int merge_sort(int l,int r){
        if(l>=r)return 0;
        int m, i, j, k;
        long res;
        
        m = (l+r)/2;
        res = (merge_sort(l,m)+merge_sort(m+1,r))%1000000007;
        
        //merge
        for(k=l;k<=r;k++)temp[k]=nums[k];
        i = l;j = m+1;k = l;
        for(k=l;k<=r;k++){
            if(i==m+1)nums[k]=temp[j++];
            else if(j==r+1||temp[i]<=temp[j])nums[k] = temp[i++];
            else {
                res=(res + m-i+1)%1000000007;
                nums[k]=temp[j++];
            }
        }
        return (int)res;
    }
   
    public int InversePairs(int [] array) {
        nums = array;
        temp = new int[array.length];
        return merge_sort(0,array.length-1);
    }
}