剑指offer-35-数组中的逆序对

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.result=0
    def InversePairs(self, data):
        # write code here
        self.splits(data)
        return self.result%1000000007
    def splits(self,data):
        if len(data)<=1:
            return data
        mid=len(data)//2
        left=self.splits(data[:mid])
        right=self.splits(data[mid:])
        return self.ranks(left, right)
    def ranks(self,left,right):
        l=0
        r=0
        ret=[]
        while l<len(left) and r<len(right):
            if left[l]>right[r]:
                ret.append(right[r])
                r+=1
                self.result+=len(left)-l  ##关键点，其他都是归并过程，只有这步计算次数
            else:
                ret.append(left[l])
                l+=1
        ret+=left[l:]
        ret+=right[r:]
        return ret