题解 | #数组中的逆序对#

public class Solution {
    int count=0;
    public int InversePairs(int [] array) {
        int l=0,h=array.length;
        if(h<2)return 0;
        mergeSort(array,l,h-1);
        return count;

    }
    public void mergeSort(int[]arr,int l,int h){
        int m=l+(h-l)/2;
        if(l<h){
            mergeSort(arr,l,m);
            mergeSort(arr,m+1,h);
            merge(arr,l,m,h);
        }
    }
    public void merge(int[]arr,int l,int m,int h){
        int [] temp = new int[h-l+1];
        int i=l,j=m+1;
        int index=0;
        while(i<=m&&j<=h){
            if(arr[i]<arr[j])
                temp[index++]=arr[i++];
            else{
                temp[index++]=arr[j++];
                count+=m-i+1;//这里一定要是m-i+1而非m-l+1，因为i是动态变化的
                count%=1000000007;
            }   
        }
        while(i<=m)
            temp[index++]=arr[i++];
        while(j<=h)
            temp[index++]=arr[j++];
        for(int k=0;k<temp.length;k++)
            arr[k+l]=temp[k];
    }
}