题解 | #数组中的逆序对# python2/3都适用 归并排序

写个题解。python版的归并排序，中间加一行：self.p += len(l1) - i。这样就行喽

# -*- coding:utf-8 -*-
class Solution:
    def InversePairs(self, data):
        # write code here
        self.p = 0
        self.divide(data)
        return self.p % 1000000007

    def divide(self, data):
        if len(data) <= 1:
            return data 
        mid = len(data) // 2
        left = self.divide(data[:mid])
        right = self.divide(data[mid:])
        return self.merge(left, right)

    def merge(self, l1, l2):
        l3 = list()
        i, j = 0, 0
        while i < len(l1) and j < len(l2):
            if l1[i] < l2[j]:
                l3.append(l1[i])
                i += 1
            else:
                self.p += len(l1) - i
                l3.append(l2[j])
                j += 1
        l3.extend(l1[i:] if i < len(l1) else l2[j:])
        return l3