I am trying to count inversions in an array using divide and conquer methodology.However, I'm unable to mantain the Total of inversions .After the program is done it returns the number of inversions in the last step and not the sum of all the inversions done before it.
def mergesort(A):
if len(A) <2:
return A
mid = len(A)//2
lefthalf = A[:mid]
righthalf = A[mid:]
mergesort(lefthalf)
mergesort(righthalf)
Total= merge(lefthalf,righthalf,A)
return Total
def merge(left,right,A):
Total = 0
i,j,k = 0,0,0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
A[k] = left[i]
i+=1
k+=1
else:
A[k] = right[j]
j+=1
k+=1
Total+= len(left[i:])
while i < len(left):
A[k] = left[i]
i+=1
k+=1
while j < len(right):
A[k] = right[j]
j+=1
k+=1
return Total
print (mergesort([1,5,3,2,4]))
How can I mantain the Total ? Please suggest neccesary changes to code with explanation. Thanks.
For completeness, here is an answer so this question doesn't remain in the unanswered section.
Your total needs to keep track of the number of inversions not just in the current stack frame, but also the stack frame of future recursive calls. To this end, either you need to add the return value of the recursive calls to Total, or declare Total as a global variable that will be shared amongst each recursive call as opposed to keeping a local variable as you have now.