归并排序，求逆序对

class Solution:
    def reversePairs(self, nums):
        def merge_sort(l,r):
            if l>=r: return
            m=(l+r)//2#中点坐标公式，分一半
            merge_sort(l, m)
            merge_sort(m+1, r)
            tmp=[0]*(r+1)#申请空间，用原数组nums来存放最后排序的结果
            tmp[l:r+1]=nums[l:r+1]
            i,j=l,m+1
            for k in range(l,r+1):
                if i==m+1:#左边排好了,右边就一直排
                   nums[k]=tmp[j]
                   j+=1
                elif j==r+1:
                     nums[k] = tmp[i]
                     i+=1
                elif tmp[i]<=tmp[j]:
                     nums[k]=tmp[i]
                     i+=1
                else:
                     nums[k] = tmp[j]
                     j+= 1
        merge_sort(0, len(nums)-1)
        return nums
a=Solution()
print(a.reversePairs([8,4,7,5,3,1,6,2]))

辅助数组tmp还可以放到函数的外面这样会节约一些时间

class Solution:
    def reversePairs(self, nums):
        def merge_sort(l,r):
            if l>=r: return
            m=(l+r)//2#中点坐标公式，分一半
            merge_sort(l, m)
            merge_sort(m+1, r)
            tmp[l:r+1]=nums[l:r+1]
            i,j=l,m+1
            for k in range(l,r+1):
                if i==m+1:#左边排好了,右边就一直排
                   nums[k]=tmp[j]
                   j+=1
                elif j==r+1:
                     nums[k] = tmp[i]
                     i+=1
                elif tmp[i]<=tmp[j]:
                     nums[k]=tmp[i]
                     i+=1
                else:
                     nums[k] = tmp[j]
                     j+= 1
        tmp = [0] * (len(nums))  # 申请空间，用原数组nums来存放最后排序的结果
        merge_sort(0, len(nums)-1)
        return nums