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

public class Solution {
    int count=0;
    public int InversePairs(int[] array) {
        mergeSort(array,0,array.length-1);
        return count;
    }
    private void mergeSort(int[] array,int left,int right){
        if(left>=right){
            return;
        }
        int mid=(left+right)/2;
        mergeSort(array,left,mid);
        mergeSort(array,mid+1,right);
        merge(array,left,mid,right);
    }
    private void merge(int[] arr,int left,int mid,int right){
        int[] num=new int[right-left+1];
        int i=left;
        int j=mid+1;
        int k=0;
        while(i<=mid&&j<=right){
            if(arr[i]<=arr[j]){
                num[k++]=arr[i++];
            }else{
                num[k++]=arr[j++];
                count=(count+mid-i+1)%1000000007;
            }
        }
        while(i<=mid){
            num[k++]=arr[i++];
        }
        while(j<=right){
            num[k++]=arr[j++];
        }
        for(k=0;k<num.length;k++){
            arr[left+k]=num[k];
        }
    }
}