具体可参考
https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solution/bao-li-jie-fa-fen-zhi-si-xiang-shu-zhuang-shu-zu-b/
代码如下：
1 class Solution { 2 public: 3 vector<int> tmp;//归并排序的辅助数组 4 5 int reversePairs(vector<int>& nums) { 6 const int len = nums.size(); 7 if(len < 2) return 0; 8 tmp.assign(len,0); 9 return merge_sort(nums,0,len - 1); 10 } 11 12 long long int merge_sort(vector<int>& nums,int l,int r) 13 { 14 if(l >= r)//归并排序递归出口 15 { 16 return 0; 17 } 18 int mid = l + (r - l)/2;//将区间一分为二 19 long long ans = merge_sort(nums,l,mid) + merge_sort(nums,mid + 1,r);//递归地求左右子数组的逆序对个数和 20 //剪枝优化： 子数组[l,r] 已经有序,横跨两个区间的逆序对个数为 0 21 if(nums[mid + 1] >= nums[mid]) 22 { 23 return ans; 24 } 25 //计算 横跨左右区间的逆序对 26 int k = 0,i = l,j = mid + 1; 27 while(i <= mid && j <= r) 28 { 29 if(nums[i] <= nums[j]) 30 { 31 tmp[k++] = nums[i++]; 32 } 33 else 34 { //执行上述递归之后，左右子数组都已经排好序 35 //此处，nums[i:mid] 都比nums[j] 大，都和num[j] 构成逆序对 36 ans += (mid - i + 1); 37 tmp[k++] = nums[j++]; 38 } 39 } 40 //将左右区间未移动到tmp的继续移到tmp 41 while(i <= mid) tmp[k++] = nums[i++]; 42 while(j <= r) tmp[k++] = nums[j++]; 43 //将排序好的元素移回原数组，放在原来的区间上,然后nums[l:r]已经排序好了 44 for(i = l,j = 0;i <= r; ) 45 { 46 nums[i++] = tmp[j++]; 47 } 48 return ans; 49 } 50 };