分治-归并系列一＞计算右侧小于当前元素的个数

class Solution {
    int[] index;//标记nums数组中的原始下标
    int[] tmpIndex;
    int[] tmpNums;
    int[] ret;

    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        index = new int[n];
        tmpIndex = new int[n];
        tmpNums = new int[n];
        ret = new int[n];

        for(int i = 0; i < n; i++)
            index[i] = i;

        mergeSort(nums,0,n-1);
        List<Integer> s = new ArrayList<>();
        for(int x : ret)
            s.add(x);
            
        return s;
    }

    private void mergeSort(int[] nums, int left, int right){
        if(left >= right) return;
        int mid = (right + left) / 2;

        int cur1 = left, cur2 = mid + 1, i = 0;

        //左半部分的个数 + 排序，右半部分的个数 + 排序
        //[left,mid][mid+1,right]
        mergeSort(nums,left,mid);
        mergeSort(nums,mid+1,right);

        //一左一右的个位数 + 排序
        while(cur1 <= mid && cur2 <= right){ 
            //降序,谁大移动谁
            if(nums[cur1] <= nums[cur2]){
                tmpNums[i] = nums[cur2];
                tmpIndex[i++] = index[cur2++];
            }else {
                ret[index[cur1]] +=  right-cur2 + 1;
                tmpNums[i] = nums[cur1];
                tmpIndex[i++] = index[cur1++];
            }
            
        }

        //处理剩余的排序⼯作
        while(cur1 <= mid){
            tmpNums[i] = nums[cur1];
            tmpIndex[i++] = index[cur1++];
        }

        while(cur2 <= right){
            tmpNums[i] = nums[cur2];
            tmpIndex[i++] = index[cur2++];
        }

        //放到原数组中
        for(int j = left; j <= right; j++){
            nums[j] = tmpNums[j-left];
            index[j] = tmpIndex[j-left];
        }
    }
}