【归并排序 】788. 逆序对的数量

归并排序是一种经典的排序算法，可以用于计算逆序对的数量。逆序对指的是在一个数组中，两个元素的顺序与它们在原数组中的顺序相反。

对于给定的数组，我们可以使用归并排序来计算逆序对的数量。具体步骤如下：

1. 将数组不断地分成两半，直到每个子数组只有一个元素。
2. 递归地将这些子数组合并起来。在合并的过程中，统计逆序对的数量。
3. 在合并两个子数组时，需要维护两个指针，分别指向两个子数组的开头。比较这两个指针所指向的元素的大小，如果前一个指针所指向的元素大于后一个指针所指向的元素，则存在逆序对。
4. 在合并过程中，将较小的元素放入一个临时数组，并将指针向后移动。如果存在逆序对，则逆序对的数量等于第一个子数组中剩余的元素个数。

以下是一个示例代码，用于计算逆序对的数量：

def merge_sort(nums):
    if len(nums) <= 1:
        return nums, 0
    
    mid = len(nums) // 2
    left, count_left = merge_sort(nums[:mid])
    right, count_right = merge_sort(nums[mid:])
    
    merged = []
    count = count_left + count_right
    i, j = 0, 0
    
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            count += len(left) - i
            j += 1
    
    merged += left[i:]
    merged += right[j:]
    
    return merged, count

def reversePairs(nums):
    _, count = merge_sort(nums)
    return count

对于题目中给定的数组，调用 `reversePairs` 函数即可计算出逆序对的数量。