51. 数组中的逆序对

利用归并排序的思想：

• 在数组分裂的过程中，把left和right从第i个位置开始进行比较，哪个小就把它加入merged中，由于此时left和right是分别有序的，如果left[i]>right[j]，证明left[i:]都大于right[j]，此时的逆序对要加len(left)-i

• 例如，left = [5, 7], right = [4, 6]

  1. i = 0, j = 0, 5>4, 此时5和7都是大于4的，逆序对加2-0=2, merged = [4]

  2. i = 0, j = 1, 5<6, 此时无逆序对，merged = [4, 5]

  3. i = 1, j = 1, 7>6, 逆序对加2-1=1，merged = [4, 5, 6]

  4. merged = [4, 5, 6, 7]

     class Solution:
     def __init__(self):
        self.count = 0
     def InversePairs(self, data):
        # write code here
        if len(data) < 2: return 0
        self.mergeSort(data)
        return self.count % 1000000007
     
     def mergeSort(self,alist):
        if len(alist) < 2:
            return alist
        middle = len(alist) // 2
        left = self.mergeSort(alist[:middle])
        right = self.mergeSort(alist[middle:])
        i, j = 0, 0
        merged = []
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                merged.append(left[i])
                i += 1
            else:
                merged.append(right[j])
                j += 1
                self.count += (len(left)-i)
        return merged  + left[i:] + right[j:]