算法描述
使用归并排序进行升序排列。
示例：
输入：nums = [5,1,1,2,0,0] 输出：[0,0,1,1,2,5]
算法设计
基本思路：借助额外空间，合并两个有序数组，得到更长的有序数组。例如：「力扣」第 88 题：合并两个有序数组。
核心函数：mergeSort函数（分治思想）和merge函数（合并有序数组），分治过程一定情况下可以实现并行化。
算法优化
- 优化1：小区间采用插入排序
Java 源码里面也有类似这种操作，「小区间」的长度是个超参数，需要测试决定，我这里参考了 JDK 源码；
- 优化2：两个数组本身有序，无需合并
左边界大于右边界或者要归并的两个数组已经有序，无需进行merge过程。
- 优化3：全程使用一份临时数组进行两个数组的合并操作
避免创建临时数组和销毁的消耗，避免计算下标偏移量。即使用System.arraycopy(nums, left, tmp, left, right - left + 1)拷贝到tmp临时数组。
- 优化4：位运算求解中间值
对Java语言，left + right >>> 1 在可能存在溢出的情况下，结论也是正确的。
代码实现
class Solution { // 列表大小大于或等于该值，将优先使用归并排序，否则使用插入排序 private static final int INSERTION_SORT_THRESHOLD = 7; public int[] sortArray(int[] nums) { int n = nums.length; int[] tmp = new int[n]; mergeSort(nums, 0, n - 1, tmp); return nums; } private void mergeSort(int[] nums, int left, int right, int[] tmp) { if (right - left <= INSERTION_SORT_THRESHOLD) { insertionSort(nums, left, right); return; } // int mid = left + (right - left) / 2; int mid = left + right >>> 1; mergeSort(nums, left, mid, tmp); mergeSort(nums, mid + 1, right, tmp); // 如果子区间本身有序，则无需合并 if (nums[mid] <= nums[mid + 1]) { return; } merge(nums, left, mid, right, tmp); } private void insertionSort(int[] nums, int left, int right) { for (int i = left + 1; i <= right; ++i) { int tmp = nums[i]; int j = i; while (j > left && nums[j - 1] > tmp) { nums[j] = nums[j - 1]; j--; } nums[j] = tmp; } } private void merge(int[] nums, int left, int mid, int right, int[] tmp) { System.arraycopy(nums, left, tmp, left, right - left + 1); int i = left; int j = mid + 1; for (int k = left; k <= right; k++) { if (i == mid + 1) { nums[k] = tmp[j]; j++; } else if (j == right + 1) { nums[k] = tmp[i]; i++; } else if (tmp[i] <= tmp[j]) { // 注意写成 < 就丢失了稳定性（相同元素原来靠前的排序以后依然靠前） nums[k] = tmp[i]; i++; } else { // tmp[i] > tmp[j]:先放较小的元素 nums[k] = tmp[j]; j++; } } } }
注意点(补充)：
- 实现归并排序的时候，要特别注意，不要把这个算法实现成非稳定排序，区别就在
<=和<，已在代码中注明。 - 「归并排序」比「快速排序」好的一点是，它借助了额外空间，可以实现「稳定排序」，Java 里对于「对象数组」的排序任务，就是使用归并排序（的升级版 TimSort，在这里就不多做介绍）。
- 时间复杂度：O(N log N)，这里 N 是数组的长度；空间复杂度：O(N)，辅助数组与输入数组规模相当。
- 「归并排序」也有「原地归并排序」和「不使用递归」的归并排序，但是我个人觉得不常用，编码、调试都有一定难度。
- 经典问题：
- 《剑指 Offer》第 51 题：数组中的逆序对，照着归并排序的思路就能写出来。
- 「力扣」第 315 题：计算右侧小于当前元素的个数，它们是一个问题。
应用拓展
示例1：「力扣」第 88 题合并两个有序数组
注意：归并排序的merge过程，但是考虑不使用额外空间，技巧：倒序遍历两个数组（先添加较大的）
代码实现：
class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int i = m - 1; int j = n - 1; int merge = m + n - 1; while (i > -1 || j > -1) { if (j < 0) { nums1[merge--] = nums1[i--]; } else if (i < 0) { nums1[merge--] = nums2[j--]; } else if (nums1[i] > nums2[j]) { nums1[merge--] = nums1[i--]; } else { nums1[merge--] = nums2[j--]; } } } }
示例2：《剑指 Offer》第 51 题：数组中的逆序对
注意：暴力解超时！必然进行时间优化，这里利用归并排序分治思想（降低时间复杂度）+合并两个数组的有序性（统计逆序对的个数）
- 排序的过程是必要的，正是因为排序才加速下一轮的统计逆序对的速度。
- 分治先统计左右区间的逆序对，再计算跨区间的逆序对（这里我们采用在第2个区间归并时，即j指向元素归并回去的时候，统计逆序数 == 前面还没有归并回去的元素个数：mid - i + 1）即以左边的元素比当前大的元素个数，统计逆序对。
ps：这里不要求排序所以需要拷贝一份nums数组。
ps2：以右侧小于当前元素个数的方式统计逆序数的个数，类似下面的315题，只需要改成归并i，统计逆序数 == j - mid + 1，如果只是统计逆序数，左右无区别，如本题。
代码实现：
class Solution { public int reversePairs(int[] nums) { int n = nums.length; if (n < 2) { return 0; } int[] copy = new int[n]; System.arraycopy(nums, 0, copy, 0, n); int[] tmp = new int[n]; return reversePairs(copy, 0, n - 1, tmp); } private int reversePairs(int[] copy, int left, int right, int[] tmp) { if (left >= right) { return 0; } int mid = left + ((right - left) >> 1); int leftPairs = reversePairs(copy, left, mid, tmp); int rightPairs = reversePairs(copy, mid + 1, right, tmp); if (copy[mid] <= copy[mid + 1]) { return leftPairs + rightPairs; } int crossPairs = mergeAndCount(copy, left, mid, right, tmp); return leftPairs + rightPairs + crossPairs; } private int mergeAndCount(int[] copy, int left, int mid, int right, int[] tmp) { System.arraycopy(copy, left, tmp, left, right - left + 1); int i = left; int j = mid + 1; int count = 0; for (int k = left; k <= right; k++) { if (i == mid + 1) { copy[k] = tmp[j]; j++; } else if (j == right + 1) { copy[k] = tmp[i]; i++; } else if (tmp[i] <= tmp[j]) { copy[k] = tmp[i]; i++; } else { copy[k] = tmp[j]; j++; // 当j指向元素归并进去，计算逆序数 count += (mid - i + 1); } } return count; } }
示例3：「力扣」第 315 题：计算右侧小于当前元素的个数
注意：数据量很大，暴力必然超时！与上题相同，即每个位置逆序数的个数。
- 需要在「前有序数组」的元素归并的时候，数一数「后有序数组」已经归并回去的元素的个数，因为这些已经出列的元素都比当前出列的元素要（严格）小；
- 一个元素在算法的执行过程中位置发生变化，我们还想定位它，可以使用「索引数组」（记录元素下标），技巧在于：「原始数组」不变，用于比较两个元素的大小，真正位置变化的是「索引数组」的位置；归并回去时，方便知道哪个下标的元素。
- ps:
res[indexes[k]] += (j - mid - 1);理解：indexes[k]表示当前k下标对应的原始数组的下标是多少，外面再套一层res[indexes[k]]记录了原始数组的对应下标右侧小于当前元素的个数，在排序的过程中，每一次计算一部分，所以是+=。整个算法完成以后，indexes映射成输入数组的元素的值以后，是有序的。
代码实现：核心：比较数值，操作下标
class Solution { public List<Integer> countSmaller(int[] nums) { List<Integer> result = new ArrayList<>(); int n = nums.length; if (n < 1) { return result; } int[] ans = new int[n]; int[] tmp = new int[n]; int[] indexs = new int[n]; for (int i = 0; i < n; i++) { indexs[i] = i; } countSmaller(nums, 0, n - 1, tmp, indexs, ans); for (int num : ans) { result.add(num); } return result; } private void countSmaller(int[] nums, int left, int right, int[] tmp, int[] indexs, int[] ans) { if (left == right) { return; } int mid = left + (right - left) / 2; countSmaller(nums, left, mid, tmp, indexs, ans); countSmaller(nums, mid + 1, right, tmp, indexs, ans); // 已经有序，不存在逆序对，不需要进行合并 if (nums[indexs[mid]] <= nums[indexs[mid + 1]]) { return; } mergeAndCount(nums, left, mid, right, tmp, indexs, ans); } private void mergeAndCount(int[] nums, int left, int mid, int right, int[] tmp, int[] indexs, int[] ans) { System.arraycopy(indexs, left, tmp, left, right - left + 1); int i = left; int j = mid + 1; for (int k = left; k <= right; k++) { if (i == mid + 1) { indexs[k] = tmp[j]; j++; } else if (j == right + 1) { indexs[k] = tmp[i]; i++; // 后有序数组已经归并完成，一定比当前要归并的元素小 ans[indexs[k]] += (right - mid); } else if (nums[tmp[i]] <= nums[tmp[j]]) { indexs[k] = tmp[i]; i++; // 当前元素要归并，后有序数组已经归并的元素一定比当前元素小 ans[indexs[k]] += (j - mid - 1); } else { indexs[k] = tmp[j]; j++; } } } }
示例4：计算数组的小和（计算左侧大于当前元素总和） 要求时间复杂度O(NlogN)，空间复杂度O(N)
1左边比1小的数，没有； 3左边比3小的数，1； 4左边比4小的数，1、3； 2左边比2小的数，1； 5左边比5小的数，1、3、4、2； 所以小和为1+1+3+1+1+3+4+2=16
代码实现：
import java.util.Scanner; public class Main { // 运行超时 public static long solution1(int[] nums) { long sum = 0; for (int i = 0; i < nums.length; i++) { for (int j = 0; j < i; j++) { if (nums[j] <= nums[i]) { sum += nums[j]; } } } return sum; } public static long solution(int[] nums) { int n = nums.length; if (n < 1) { return 0; } int[] tmp = new int[n]; return mergeSort(nums, 0, n - 1, tmp); } private static long mergeSort(int[] nums, int left, int right, int[] tmp) { if (left == right) { return 0; } int mid = left + (right - left) / 2; return mergeSort(nums, left, mid, tmp) + mergeSort(nums, mid + 1, right, tmp) + mergeAndSum(nums, left, mid, right, tmp); } private static long mergeAndSum(int[] nums, int left, int mid, int right, int[] tmp) { System.arraycopy(nums, left, tmp, left, right - left + 1); int i = left; int j = mid + 1; long smallSum = 0; for (int k = left; k <= right; k++) { if (i == mid + 1) { nums[k] = tmp[j]; j++; } else if (j == right + 1) { nums[k] = tmp[i]; i++; } else if (tmp[i] <= tmp[j]) { // i进行归并时，左边小于右边产生小和（当前加入的一定比右边还未加入的元素小） smallSum += tmp[i] * (right - j + 1); nums[k] = tmp[i]; i++; } else { nums[k] = tmp[j]; j++; } } return smallSum; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] nums = new int[n]; int i = 0; while (n-- > 0) { nums[i++] = sc.nextInt(); } System.out.println(solution(nums)); // System.out.println(solution1(nums)); } }
