mergesortの逆数を数える - python、algorithm、mergesort

正しく機能するマージソート関数を実装しましたが、ソートされる前に元の配列の反転数を数えるために修正するのに苦労しています。

反転は、 i < j but a[i] > a[j] 例、 a = [5,2,1] 3つの反転があります。 (5,2),(5,1),(2,1)

def mergeSort(a):

mid = len(a)//2

if len(a) < 2:
return

l = a[:mid]
r = a[mid:]
mergeSort(l)
mergeSort(r)

return merge(l,r,a)

def merge(l,r,a):
i = 0
j = 0
k = 0

inv = 0

while(i < len(l) and j < len(r)):
if(l[i] < r[j]):
a[k] = l[i]
i = i + 1
else:
a[k] = r[j]
inv = inv + 1
j = j + 1
k = k + 1

while i < len(l):
a[k] = l[i]
i = i + 1
k = k + 1
while j < len(r):
a[k] = r[j]
j = j + 1
k = k + 1
inv = inv + 1
return [a,inv]

a = [6,5,4,3,2,1]
print(mergeSort(a))

上記の例では、n（n-1）/ 2が降順配列の反転数であるため、反転数として15を返す必要があります。

誰かがそれを数える方法を説明できますか？

回答：

L[i] > R[j] は単一の反転ですが、配列はソートされているので、 L[k] > R[j] いくつかのための k、 これの意味は L[k] > R[j] for all i <= k < |L|。だからあなたは配列の長さを引くことができる L から i あなたに反転の総数を与えるために。