归并排序及其衍生问题 Merge-Sort related issue
#算法导论习题2-4 求逆序对的问题； Leetcode: 315. Count of Smaller Numbers After Self 327. Count of Range Sum 493.Reverse Pairs
A[i…j], 以上问题暴力求解，遍历数组,对于k属于[i,j],k之前大于A[k]的值，需要二次遍历，因此时间复杂度O(n); 此处也可以引入二叉搜索树 将search复杂度降为O(logn); 但该方法不是本次所讨论的，本文说明如何用Merge Sort思想解决相关问题；
对于上述问题，均可以采用divide and conquer的思想，将问题一分为二，数组分为左半部分和右半部分，分别进行求解以及排序，求解以及合并时间复杂度O(n），总的复杂度为O(nlogn）；
public List<Integer> countSmaller(int[] nums) { int n = nums.length; List<Integer> res = new ArrayList<>(); if (n == 0) return res; Integer[] arr = new Integer[n]; Arrays.fill(arr, 0); int[] index = new int[n]; for (int i = 0; i < n; i++) { index[i] = i; } countSmaller(nums, index, 0, n - 1, arr); return Arrays.asList(arr); } private void countSmaller(int[] nums, int[] index, int left, int right, Integer[] arr) { if (left >= right) return; int mid = left + ((right - left) >> 1); countSmaller(nums, index, left, mid, arr); countSmaller(nums, index, mid + 1, right, arr); int i = left; int j = mid + 1; int p = 0; int[] newIndex = new int[right - left + 1]; while (i <= mid) { while (j <= right && nums[index[i]] > nums[index[j]]) { newIndex[p++] = index[j++]; } arr[index[i]] += j - (mid + 1); newIndex[p++] = index[i++]; } while (j <= right) newIndex[p++] = index[j++]; for (i = left; i <= right; i++) { index[i] = newIndex[i - left]; } }