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 also used indices. Additionally, I used nested functions to avoid generating new arrays by keeping the original and the auxiliary one in scope (along with a "Context" class to make the counter variable accessible).
Instead of using built-in functions or slicing to build the new array, I just iterated through it and assigned each element a new value. I made this possible by initializing the new array as a pointer to the original and initializing the auxiliary one as a copy of the original; this way, we have a pre-determined size that allows for iteration.
P.S. This was written in Python 2 (without using PyPy). This times out on the last three cases.
#!/bin/pythonimportsysdefmerge_sort(arr):classContext:count=0defmerge(*indices):# indices = first, last, and pivot indices, respectivelyhead,tail=indices[0],indices[1]pivot=indices[2]i=headj=pivot+1k=0while(i<=pivotandj<=tail):ifnew[i]<=new[j]:aux[k]=new[i]i+=1k+=1else:aux[k]=new[j]j+=1k+=1Context.count+=pivot-i+1while(i<=pivot):aux[k]=new[i]i+=1k+=1while(j<=tail):aux[k]=new[j]j+=1k+=1forxinxrange(head,tail+1):new[x]=aux[x-head]# end mergedefsplit(a,*indices):# indices = first and last indices, respectivelyhead,tail=indices[0],indices[1]pivot=(head+tail)/2ifhead<tail:l_sub=a[head:pivot+1]r_sub=a[pivot+1:tail+1]split(l_sub,head,pivot)split(r_sub,pivot+1,tail)merge(head,tail,pivot)# end splitnew=arraux=list(new)tail=len(new)-1split(new,0,tail)returnContext.count# end merge_sortif__name__=="__main__":loops=int(raw_input().strip())for_inxrange(loops):useless_var=int(raw_input().strip())arr=map(int,raw_input().strip().split(' '))result=merge_sort(arr)printresult
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Merge Sort: Counting Inversions
You are viewing a single comment's thread. Return to all comments →
I also used indices. Additionally, I used nested functions to avoid generating new arrays by keeping the original and the auxiliary one in scope (along with a "Context" class to make the counter variable accessible).
Instead of using built-in functions or slicing to build the new array, I just iterated through it and assigned each element a new value. I made this possible by initializing the new array as a pointer to the original and initializing the auxiliary one as a copy of the original; this way, we have a pre-determined size that allows for iteration.
P.S. This was written in Python 2 (without using PyPy). This times out on the last three cases.