归并排序思想

解题思路:

注意事项:

参考代码:

def mergeSort(arr):
   if len(arr) <= 1:
       return arr, 0
   mid = len(arr) // 2
   left, left_inv = mergeSort(arr[:mid])
   right, right_inv = mergeSort(arr[mid:])
   merged, merge_inv = merge(left, right)
   return merged, left_inv + right_inv + merge_inv

def merge(left, right):
   merged = []
   inversions = 0
   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])
           inversions += len(left) - i
           j += 1
   while i < len(left):
       merged.append(left[i])
       i += 1
   while j < len(right):
       merged.append(right[j])
       j += 1
   return merged, inversions

n = int(input())
arr = list(map(int, input().split()))
_, inversions = mergeSort(arr)
print(inversions)