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

    int sum = 0;
    int P = 1000000007;
    public int InversePairs(int[] array) {
       merge(array,0,array.length-1);
        return sum;
    }
    public void merge(int[] array,int l,int r){
        if(l >= r){
            return;
        }
        int mid = l + ((r - l)>>1);
        merge(array,l,mid);
        merge(array,mid+1,r);
        int[] tmp = new int[r-l+1];
        int k = 0;
        int i = l;
        int j = mid+1;
        while(i <= mid && j <= r){
            if(array[i] <= array[j]){
                tmp[k++] = array[i++];
            }else{
                tmp[k++] = array[j++];
                sum = (sum + mid - i + 1)%P;
            }
        }
        while(i <= mid){
            tmp[k++] = array[i++];
        }
        while(j <= r){
            tmp[k++] = array[j++];
        }
        for(i = 0,j = l;i < r-l+1;i++,j++){
            array[j] = tmp[i];
       }
    }
}