在数组中的两个数字如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
例如在数组{7,5,6,4}中，一共存在5个逆序对，分别是(7,6),(7,5),(7,4),(6,4),(5,4)
顺序扫描整个数组，每扫描到一个数字的时候，逐个比较该数字和它后面的数字的大小。如果后面的数字比它小，则这两个数字就组成了一个逆序对。假设数组中有n个数字。由于每个数字都要和O(n)个数字作比较，因此这个算法的时间复杂度是O(n^2)
考虑想比较两个相邻的数字，先把数组分解成两个长度为2的子数组，再把这两个子数组分别拆分成两个长度为1的子数组，接下里一边合并相邻的子数组，一边统计逆序对的数目。
在第一对长度为1的子数组{7}和{5}中7大于5，因此(7,5)组成一个逆序对。
在第二对长度为1的子数组{6}和{4}中也有逆序对（6,4）
由于已经统计了，所以需要对这两个子数组进行排序，避免重复统计
合并两个子数组并统计逆序对的过程
5,7，P1指向7
4,6，P2指向6
然后先对比P1和P2，发现7大于6，就把7放入数组的最右边，然后P1左移一位，继续比较，最后复制最后一个数字到辅助数组
（a）P1指向的数字大于P2指向的数字，表明数组中存在逆序对。P2指向的数字是第二个子数组的第二个数字，因此第二个子数组中有两个数字比7小。把逆序对数目加2，并把7复制到辅助数组，向前移动P1和P3
（b）P1指向的数字小于P2指向的数字，没有逆序对。把P2指向的数字复制到辅助数组，向前移动P2和P3
（c）P1指向的数字大于P2指向的数字，因此存在逆序对。由于P2指向的数字是第二个子数组中的第一个数字，子数组只有一个数字比5小，把逆序对数目加1，并把5复制到辅助素组，向前移动P1和P3
接下来统计两个长度为2的子数组之间的逆序对。
先用两个指针分别指向两个子数组的末尾，并每次比较两个指针指向的数字。如果第一个子数组中的数字大于第二个子数组中的数字，则构成逆序对，并且逆序对的数目等于第二个子数组中剩余数字的 。如果第一个数组中的数字小于或等于第二个数组中的数字，则不构成逆序对。每一次比较的时候，都把较大的数字从后往前复制到一个辅助数组中，确保辅助数组中的数字是递增排序的。把较大的数字复制到辅助数组只有，把对应的指针向前移动一位，接下来进行下一轮比较。
统计逆序对的过程：先把数组分隔成子数组，先统计出子数组内部的逆序对的数目，然后再统计出两个相邻子数组之间的逆序对的数目。在统计逆序对的过程，还需要排序，这就是归并排序
count = 0 class Solution: def InversePairs(self, data): global count def MergeSort(lists): global count if len(lists) <= 1: return lists num = int( len(lists)/2 ) left = MergeSort(lists[:num]) right = MergeSort(lists[num:]) r, l=0, 0 result=[] while l<len(left) and r<len(right): if left[l] < right[r]: result.append(left[l]) l += 1 else: result.append(right[r]) r += 1 count += len(left)-l result += right[r:] result += left[l:] return result MergeSort(data) return count%1000000007