算法1

(归并排序) $时间复杂度：O(nlogn) 额外空间复杂度：O(n)$

利用分而治之的思想，即归并排序。
本题目的难点在于while循环中，
1. 先把整个数组不断地向下分离，只有一个的时候，进行合并，即left==right
2. 哪个大哪个放在前面，即

if(nums[i] <= nums[j]){
    h[hi++] = nums[j++];
}else{
    pairs+=(right-j+1);
    h[hi++] = nums[i++];
}

1. 从最一开始，我们就按照从大到小进行排列，看步骤2，所以，如果左边数组的数值大于右边数组的某一个数值，那么它将大于右边数组这个数值后面所有的数值，所以pairs+=(right-j+1);，即用右边所有的数值数量减去当前数值的位置，然后将左边的数值向后移动一位，右边不动，继续比较，进行合并。
2. 每次合并之后，就将这个数组赋给原数组

java 代码

class Solution {
    public int inversePairs(int[] nums) {
        if(nums == null||nums.length==0)
            return 0;

        return func(nums,0,nums.length-1);
    }

    public int func(int[] nums, int left, int right){
        if(left == right)
            return 0;

        int mid = (left+right)/2;
        return func(nums,left,mid)+func(nums,mid+1,right)+merge(nums,left,mid,right);
    }

    public int merge(int[] nums, int left, int mid ,int right){
        int[] h = new int[right-left+1];
        int hi = 0;
        int i = left;
        int j = mid+1;
        int pairs = 0;
        while(i<=mid && j<=right){
            if(nums[i] <= nums[j]){
                h[hi++] = nums[j++];
            }else{
                pairs+=(right-j+1);
                h[hi++] = nums[i++];
            }
        }
        for(;(j<right+1)||(i<mid+1);j++,i++){
            h[hi++] = i > mid ? nums[j]:nums[i];
        }

        for(int k = 0; k!=h.length;k++){
            nums[left++] = h[k];
        }

        return pairs;
    }
}