输出逆序数

逆序数是指在一个数组中，如果有两个数a[i]和a[j]，并且i<j，但是a[i]>a[j]，那么这个数组中就存在一个逆序对。下面是一个输出数组中逆序对个数的示例代码：

def mergeSort(arr):
    if len(arr) <= 1:
        return arr, 0
    mid = len(arr) // 2
    left, count1 = mergeSort(arr[:mid])
    right, count2 = mergeSort(arr[mid:])
    count = count1 + count2
    i = j = 0
    res = []
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            res.append(left[i])
            i += 1
        else:
            res.append(right[j])
            j += 1
            count += len(left) - i
    res += left[i:]
    res += right[j:]
    return res, count

def countInversions(arr):
    res, count = mergeSort(arr)
    return count

这个代码使用了归并排序的思想，在归并排序的过程中，统计逆序对的个数。时间复杂度为O(nlogn)。