class Solution {

     //归并排序：

     int reversepairs = 0;//逆序对数

     public int[] mergeSort(int[] nums, int left, int right){//归并排序函数

         if (left == right)//如果左边界等于右边界，说明数组只有一个值，不用排序

             return new int[] { nums[left] };

         int mid =  (right + left) / 2;//将数组分为两半

         int[] leftArr = mergeSort(nums, left, mid); //左有序数组

         int[] rightArr = mergeSort(nums, mid + 1, right); //右有序数组

         int[] newNum = new int[leftArr.length + rightArr.length]; //新的有序数组

         int m = 0, i = 0, j = 0;

         //挨着挨着比较从左右两边的排好序的数组中从头开始比较，谁小就先放谁进新的有序空数组

         while (i < leftArr.length && j < rightArr.length){//直到左右两个有序数组有一个的遍历下标超出该数组的序列尾部

             if(leftArr[i] <= rightArr[j])//左序列的元素小，就把左序列的该元素放入新的空的有序数组中

                 newNum[m++] = leftArr[i++];

             else{//右序列的元素小，就把右序列的该元素放入新的空的有序数组中

                 newNum[m++] = rightArr[j++];

                 reversepairs += leftArr.length - i;//左边序列数组中还有leftArr.length-i个元素大于rightArr[j],所以这也是该区间的逆序对数             }

         }

         while (i < leftArr.length)//如果左序列的元素还有剩余的元素没放进新的空数组中，就把左序列剩余元素放入新的空的有序数组中

             newNum[m++] = leftArr[i++];

         while (j < rightArr.length)//如果右序列的元素还有剩余的元素没放进新的空数组中，就把右序列剩余元素放入新的空的有序数组中

             newNum[m++] = rightArr[j++];

         return newNum;

     }

     public int reversePairs(int[] nums) {//入口函数

         if(nums.length == 0)//如果给定的是个空数组，据题意返回0

             return 0;

         int[] newNums = mergeSort(nums, 0, nums.length - 1);//调用归并排序函数，返回一个有序的数组

         return reversepairs;//返回逆序对数

     }

 }