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

##借鉴了大神的一些写法
# -*- coding:utf-8 -*-

global p
p=0
def merge(left, right):
    global p
    ll, rr = 0, 0
    result = []
    while ll < len(left) and rr < len(right):
        if left[ll] < right[rr]:
            result.append(left[ll])
            ll += 1
        else:
            result.append(right[rr])
            p=p+len(left)-ll
            rr += 1
    result+=left[ll:]
    result+=right[rr:]
    return result

def merge_sort(alist):
    if len(alist) <= 1:
        return alist
    num = len(alist) // 2   # 从中间划分两个子序列
    left = merge_sort(alist[:num]) # 对左侧子序列进行递归排序
    right = merge_sort(alist[num:]) # 对右侧子序列进行递归排序
    return merge(left, right) #归并
class Solution:
    def InversePairs(self, data):
        # write code here
        merge_sort(data)
        

        return p % 1000000007