归并排序求逆序对个数

class Solution {
    public int reversePairs(int[] nums) {
        return merge(nums,0,nums.length - 1);
    }

    public int merge(int[] nums,int l,int r) {   //返回区间[l,r]间逆序对的个数
        if(l >= r) {
            return 0;
        }
        int mid = (l + r) >> 1;
        //逆序对个数有两部分组成，两个区间内部的逆序对个数，两个区间之间的逆序对个数
        int res = merge(nums,l,mid) + merge(nums,mid + 1,r);    
        List<Integer> list = new ArrayList<>();
        int i = l,j = mid + 1;
        while(i <= mid && j <= r) {
            if(nums[i] <= nums[j]) {
                list.add(nums[i++]);
            } else {
                list.add(nums[j++]);
                res += mid - i + 1;     //i以及后面的元素都大于nums[j]，都是逆序对
            }
        }
        while(i <= mid) {
            list.add(nums[i++]);
        }
        while(j <= r) {
            list.add(nums[j++]);
        }
        i = l;
        j = 0;
        while(i <= r) {
            nums[i++] = list.get(j++);
        }
        return res;
    }
}