【剑指offer】数组中的逆序对

入门思路：冒泡排序的交换次数，即数组逆序对数 -> 时间复杂度O(n^2) -> 归并排序求解O(logn)
// 这个题目有很多经典的解法：冒泡排序、归并排序、树状数组、线段树等等，可惜现在老了，写不了啦。

public class Solution {

    static int mod = (int) 1e9 + 7;
    static int count = 0;
    static int[] arr = new int[220000];

    public static void Merge(int l, int mid, int r, int[] array) {
        int i = l, j = mid + 1, k = l;
        while (i <= mid && j <= r) {
            if (array[i] <= array[j]) {
                arr[k++] = array[i++];
            } else {
                count = (count + mid - i + 1) % mod;
                arr[k++] = array[j++];
            }
        }
        while (i <= mid) {
            arr[k++] = array[i++];
        }
        while (j <= r) {
            arr[k++] = array[j++];
        }
        for (i = l; i <= r; i++) {
            array[i] = arr[i];
        }
    }

    public static void MergeSort(int l, int r, int[] array) {
        if (l < r) {
            int mid = (l + r) >> 1;
            MergeSort(l, mid, array);
            MergeSort(mid + 1, r, array);
            Merge(l, mid, r, array);
        }
    }

    public static int InversePairs(int[] array) {
        if (array == null || array.length == 0) {
            return 0;
        }
        MergeSort(0, array.length - 1, array);
        return count;
    }

}