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.
tested on both pypy2 and 3, starts to timeout on some of the earlier test cases.
code is below:
defsort_pair(arr0,arr1):iflen(arr0)>len(arr1):returnarr1,arr0else:returnarr0,arr1defmerge(arr0,arr1):inversions=0result=[]whilelen(arr0)>0andlen(arr1)>0:ifarr0[0]<=arr1[0]:result.append(arr0.pop(0))else:# count the inversion right here: add the length of left arrayinversions+=len(arr0)result.append(arr1.pop(0))iflen(arr0)==0:result+=arr1eliflen(arr1)==0:result+=arr0returnresult,inversionsdefsort(arr):length=len(arr)mid=length//2iflength>=2:sorted_0,counts_0=sort(arr[:mid])sorted_1,counts_1=sort(arr[mid:])result,counts=merge(sorted_0,sorted_1)returnresult,counts+counts_0+counts_1else:returnarr,0defcount_inversions(a):final_array,inversions=sort(a)# print(final_array)returninversionst=int(input().strip())fora0inrange(t):n=int(input().strip())arr=list(map(int,input().strip().split('')))print(count_inversions(arr))
Merge Sort: Counting Inversions
You are viewing a single comment's thread. Return to all comments →
tested on both pypy2 and 3, starts to timeout on some of the earlier test cases.
code is below: