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

归并排序中有一步是比较两个有序子数组中两个数的大小，当属于后半部分的那个数小于前半部分的那个数时，由于是有序子数组，那么前半部分那个数后面的数也大于后半部分的那个数，所以这些数都能组成逆序对。所以每次将这些逆序对个数累加即可。

public class Solution {
    int cnt = 0;
    int[] tmp;
    int MOD = (int)(1e9 + 7);
    public int InversePairs(int [] a) {
        int n = a.length;
        tmp = new int[n];
        merge_sort(a,0,n-1);
        return cnt;
    }
    
    public void merge_sort(int[] a,int l,int r) {
        if(l >= r) {
            return;
        }
        int mid = l + r >> 1;
        merge_sort(a,l,mid);
        merge_sort(a,mid+1,r);
        int i = 0, j = l, k = mid + 1;
        while(j <= mid && k <= r) {
            if(a[j] <= a[k]) {
                tmp[i++] = a[j++];
            } else {
                cnt = (cnt + mid - j + 1) % MOD;
                tmp[i++] = a[k++];
            }
        }
        while(j <= mid) {
            tmp[i++] = a[j++];
        }
        while(k <= r) {
            tmp[i++] = a[k++];
        }
        for(i = 0,j = l;j <= r;i++,j++) {
            a[j] = tmp[i];
        }
    }
}