##### Short Problem Definition:

Compute number of inversion in an array.

##### Link

##### Complexity:

expected worst-case time complexity is O(N*log(N));

expected worst-case space complexity is O(N)

##### Execution:

Any sorting algorithm with a NlogN runtime will do the trick. It is important to count all (remaining) bigger elements on the left side. Do not forget to check for the maximal return value!

##### Solution:

MAX_NR = 1000000000 def mergeSort(alist): inversion_count = 0 if len(alist)>1: mid = len(alist)//2 lefthalf = alist[:mid] righthalf = alist[mid:] inversion_count += mergeSort(lefthalf) if (inversion_count > MAX_NR): raise inversion_count += mergeSort(righthalf) if (inversion_count > MAX_NR): raise i=0 j=0 k=0 while i<len(lefthalf) and j<len(righthalf): if lefthalf[i]<=righthalf[j]: alist[k]=lefthalf[i] i=i+1 else: alist[k]=righthalf[j] j=j+1 inversion_count += len(lefthalf)-i if (inversion_count > MAX_NR): raise k=k+1 while i<len(lefthalf): alist[k]=lefthalf[i] i=i+1 k=k+1 while j<len(righthalf): alist[k]=righthalf[j] j=j+1 k=k+1 return inversion_count def solution(A): try: return mergeSort(A) except: return -1

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.