public List<Integer> countSmaller(int[] nums) {
List<Integer> res = new ArrayList<>();
if (nums == null || nums.length == 0) {
// count[i]表示,在nums排序前,i位置上的数的count of smaller numbers
int[] count = new int[n];
// index存的是nums中每个数对应的位置,index[i]表示,在nums排序前,第i位置上的数在归并过程中的位置
int[] index = new int[n];
for (int i = 0; i < n; i++) {
mergeSort(nums, index, count, 0, n - 1);
public void mergeSort(int[] nums, int[] index, int[] count, int start, int end) {
int mid = start + (end - start) / 2;
mergeSort(nums, index, count, start, mid);
mergeSort(nums, index, count, mid + 1, end);
merge(nums, index, count, start, mid, end);
public void merge(int[] nums, int[] index, int[] count, int start, int mid, int end) {
int[] temp = new int[end - start + 1];
while (i <= mid && j <= end) {
// index[j]在归并排序的后半部分,如果nums[index[j]] < nums[index[i]] 说明index[j]所对应的数在nums中原本是在index[i]对应的数后面,而nums[index[j]] < nums[index[i]], 说明我们找到一个符合条件的count of smaller number, 所以rightCount加一
if (nums[index[j]] < nums[index[i]]) {
// 注意这里temp存储的是数字对应的位置,不是数字的值,这和传统的merge sort不同
// 当nums[index[j]] >= nums[index[i]]时,因为index[i]对应的数在[index[j]对应的数前面,而index[i]的count of smaller number就是rightCount
count[index[i]] += rightCount;
count[index[i]] += rightCount;
// 将合并完成后的数组所对应的位置重新存放在index中
for (int m = start; m <= end; m++) {
index[m] = temp[m - start];