We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
i, j, k = 0, 0, 0
la1 = len(a1)
la2 = len(a2)
while i < la1 and j < la2:
elemA = a1[i]
elemB = a2[j]
if elemA > elemB:
comb.append(elemB)
j += 1
global count
count += la1 - i
else:
comb.append(elemA)
i += 1
while i < la1:
comb.append(a1[i])
i += 1
while j < la2:
comb.append(a2[j])
j += 1
return comb
Merge Sort: Counting Inversions
You are viewing a single comment's thread. Return to all comments →
For me also removing unnecessary len() calls made it work on python 2.
def countInversions(arr): mergeSort(arr) return count
def mergeSort(arr): if len(arr) == 1: return arr else: mid = len(arr)/2 return merge(mergeSort(arr[:mid]), mergeSort(arr[mid:]))
def merge(a1, a2): comb = []