题解 | #数组中的逆序对#

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param data int整型一维数组 
# @return int整型
#
class Solution:
    def InversePairs(self , data: List[int]) -> int:
        # write code here
        def mergeSort(L,R):
            if L>=R:
                return 0
            m=L+(R-L)//2
            cnt=mergeSort(L,m)+mergeSort(m+1,R)
            i,j=L,m+1
            pos=L
            while i<=m and j<=R:
                if data[i] <= data[j]:
                    tmp[pos]=data[i]
                    i+=1
                else:
                    tmp[pos]=data[j]
                    j+=1
                    cnt+=(m-i+1)
                pos+=1
            for k in range(i,m+1):
                tmp[pos]=data[k]
                pos+=1
            for k in range(j,R+1):
                tmp[pos]=data[k]
                pos+=1
            data[L:R+1]=tmp[L:R+1]
            return cnt
        n=len(data)
        tmp=[0]*n
        res=mergeSort(0,n-1)
        return res%1000000007