数组中的逆序对

题目描述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

思路：实际上是一个分治问题，不断将数组一分为二，直到数组中只有两个元素，统计逆序对个数，分别排序后进行合并，merge的时候计算合并的两个数组间的逆序对个数。类似归并排序的过程。

def InversePairs(self, data):
    # write code here
    if len(data) == 0:
        return 0

    def mergeSort(data, begin, end):
        if begin == end - 1:
            return 0
        mid = int((begin + end) / 2)
        left_count = mergeSort(data, begin, mid)
        right_count = mergeSort(data, mid, end)
        merge_count = merge(data, begin, mid, end)
        return left_count + right_count + merge_count

    def merge(data, begin, mid, end):
        i = begin
        j = mid
        count = 0
        temp = []
        while i < mid and j < end:
            if data[i] <= data[j]:
                temp.append(data[i])
                i += 1
            else:
                temp.append(data[j])
                j += 1
                count += mid - i
        while i < mid:
            temp.append(data[i])
            i += 1
        while j < end:
            temp.append(data[j])
            j += 1
        data[begin: end] = temp
        del temp
        return count

    begin = 0
    end = len(data)
    ans = mergeSort(data, begin, end)
    return ans % 1000000007