归并：把两个或多个已经有序的序列合并成⼀个
排序算法：归并排序【图解+代码】_哔哩哔哩_bilibili
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型一维数组
* @return int整型
*/
public int InversePairs (int[] nums) {
// write code here
if (nums.length == 0) return 0;
//使用归并排序
mergeSort(nums, 0, nums.length - 1);
}
public void mergeSort(int[] array, int left, int right) {
if (left >= right) return; // 只有一个数字，则停止划分
int mid = left + (right - left) / 2;
//递归分解
mergeSort(array, left, mid);
mergeSort(array, mid + 1, right);
//合并
merge(array, left, mid, right);
}
public void merge(int[] array, int left, int mid, int right) {
//标记左半区域未排序第一个元素
int l_pos = left;
//标记右半区域未排序第一个元素
int r_pos = mid + 1; //两个区域是从mid分开的，右边肯定从mid开始
//临时数组下标
int pos = left;
int[] tempArray = new int[array.length];
//合并
while (l_pos <= mid &&
r_pos <= right) { //两个区域任意一个循环完就停止
if (array[l_pos] < array[r_pos]) {
tempArray[pos++] = array[l_pos++];
} else {
tempArray[pos++] = array[r_pos++];
}
}
//承接上面，循环完，可能左边区域或者右边区域剩余(注意左边或者右边都是排好序的) 所以剩余区域直接复制到数组后
//左边剩余
while (l_pos <= mid) {
tempArray[pos++] = array[l_pos++];
}
//右边剩余
while (r_pos <= right) {
tempArray[pos++] = array[r_pos++];
}
//最后，tempArr复制覆盖掉array即可
while (left <= right) {
array[left] = tempArray[left];
left++;
}
}
}