特点

平均时间复杂度 - O(nlogn)
最坏时间复杂度 - O(nlogn)
空间复杂度 - O(n)
Merge Sort是一种stable sorting algorithm. Stable意味着对于相同值的元素，在排序后他们的相对顺序还是一致的。比如我们有[2, 1, 2]，在merge sort后我们得到[1, 2, 2]，结果中的第1个2一定是原数组中排在相对靠前的那个2，而第2个2一定是原数组中排在相对靠后的那个2。

利用merge sort stability的特性来解决一些问题

Count of Smaller Numbers After Self

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> result = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return result;
        }
        int m = nums.length;
        int[] indexes = new int[m];
        for (int i = 0; i < m; i++) {
            indexes[i] = i;
        }
        int[] count = new int[m];
        mergesort(nums, indexes, count, 0, m - 1, new int[m]);
        for (int c: count) {
            result.add(c);
        }
        return result;
    }
    
    private void mergesort(int[] nums, int[] indexes, int[] count, int start, int end, int[] temp) {
        if (start >= end) {
            return;
        }
        int mid = start + (end - start) / 2;
        mergesort(nums, indexes, count, start, mid, temp);
        mergesort(nums, indexes, count, mid + 1, end, temp);
        merge(nums, indexes, count, start, mid, end, temp);
    }
    
    private void merge(int[] nums, int[] indexes, int[] count, int start, int mid, int end, int[] temp) {
        int left = start, right = mid + 1, index = start, rightCount = 0;
        while (left <= mid && right <= end) {
            if (nums[indexes[left]] <= nums[indexes[right]]) {
                count[indexes[left]] += rightCount;
                temp[index++] = indexes[left++];
            } else {
                rightCount++;
                temp[index++] = indexes[right++];
            }
        }
        while (left <= mid) {
            count[indexes[left]] += rightCount;
            temp[index++] = indexes[left++];
        }
        while (right <= end) {
            temp[index++] = indexes[right++];
        }
        for (int k = start; k <= end; k++) {
            indexes[k] = temp[k];
        }
    }
}

这题我们要得到对于原数组中的每一个数，找到各有多少个数在排在它的后面且比它小。在merge sort的过程中，其实我们就是用the first half subarray中的每一个数，与the second half subarray中的每一个数相比较。

每次我们处理一个处在the first half subarray中的数，并把它放到temp数组中时，我们可以知道排在它之前的有多少个之前是处在the second half subarray中的数 - 即rightCount。
这题里有另一个比较ticky的点是，我们仍然要维护一个原数组的index的状态，所以我们并不直接对nums进行排序，而是另外维护一个indexes array，这样我们就仍然维护了原先的index的状态。每次access一个val，我们就是通过nums[indexes[left/right]]来做到的。

Count of Range Sum

class Solution {
    
    int lower, upper;
    int count = 0;
    
    public int countRangeSum(int[] nums, int lower, int upper) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int m = nums.length;
        long[] sums = new long[m + 1];
        long sum = 0;
        for (int i = 0; i < m; i++) {
            sum += nums[i];
            sums[i + 1] = sum;
        }
        this.lower = lower;
        this.upper = upper;
        mergesort(sums, 0, m, new long[m + 1]);
        return count;
    }
    
    private void mergesort(long[] sums, int start, int end, long[] temp) {
        if (start >= end) {
            return;
        }
        int mid = start + (end - start) / 2;
        mergesort(sums, start, mid, temp);
        mergesort(sums, mid + 1, end, temp);
        merge(sums, start, mid, end, temp);
    }
    
    private void merge(long[] sums, int start, int mid, int end, long[] temp) {
        int left = start, right = mid + 1, index = start, lowerPointer = mid + 1, higherPointer = mid + 1;
        while (left <= mid) {
            while (lowerPointer <= end && sums[lowerPointer] - sums[left] < lower) {
                lowerPointer++;
            }
            while (higherPointer <= end && sums[higherPointer] - sums[left] <= upper) {
                higherPointer++;
            }
            count += higherPointer - lowerPointer;
            
            while (right <= end && sums[right] <= sums[left]) {
                temp[index++] = sums[right++];
            }
            temp[index++] = sums[left++];
        }
        while (right <= end) {
            temp[index++] = sums[right++];
        }
        for (int k = start; k <= end; k++) {
            sums[k] = temp[k];
        }
    }
}

这题要找有多少个subarray的和是在一个[lower, upper]的范围里。首先要看subarray的和，我们立即想到了prefixSums。brute force的方法就是在O(n^2)的时间复杂度下，遍历prefixSum。利用merge sort stability的特点，我们可以在prefixSum array上做merge sort。在merge sort过程中，对于每一个在first half subarray里的值，我们去看有多少个在second half subarray的数是符合条件的。

Reverse Pairs

class Solution {
    public int reversePairs(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int m = nums.length;
        return mergesort(nums, 0, m - 1, new int[m]);
    }
    
    private int mergesort(int[] nums, int start, int end, int[] temp) {
        if (start >= end) {
            return 0;
        }
        int mid = start + (end - start) / 2;
        int result = mergesort(nums, start, mid, temp) + mergesort(nums, mid + 1, end, temp);
        return result + merge(nums, start, mid, end, temp);
    }
    
    private int merge(int[] nums, int start, int mid, int end, int[] temp) {
        int left = start, right = mid + 1, index = start, pointer = mid + 1, count = 0;
        while (left <= mid) {
            while (pointer <= end && nums[left] > 2L * nums[pointer]) {
                pointer++;
            }
            count += pointer - (mid + 1);
            while (right <= end && nums[right] <= nums[left]) {
                temp[index++] = nums[right++];
            }
            temp[index++] = nums[left++];
        }
        while (right <= end) {
            temp[index++] = nums[right++];
        }
        for (int k = start; k <= end; k++) {
            nums[k] = temp[k];
        }
        return count;
    }
}

这题我们要找有多少对pair，满足以下的条件 - i < j 且 nums[i] > 2*nums[j]
和Count of Range Sum一样，在merge sort的过程中，我们找对于每一个left element，有多少个right element满足条件。

Merge Sort

特点

利用merge sort stability的特性来解决一些问题