算法描述
使用归并排序进行升序排列。
示例：
输入：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));
}
}
巨人的肩膀：
