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.
@episodeyang: your algorithm is correct but it's slowed down by running array.pop(0). That's an O(n) operation in python. I modified your merge function to use two indices to keep track of where I was in each array and ran it in pypy3 and it passed. See code below:
defmerge(arr0,arr1):inversions=0result=[]# two indices to keep track of where we are in the arrayi0=0i1=0# probably doesn't really save much time but neater than calling len() everywherelen0=len(arr0)len1=len(arr1)whilelen0>i0andlen1>i1:ifarr0[i0]<=arr1[i1]:result.append(arr0[i0])i0+=1else:# count the inversion right here: add the length of left arrayinversions+=len0-i0result.append(arr1[i1])i1+=1iflen0==i0:result+=arr1[i1:]eliflen1==i1:result+=arr0[i0:]returnresult,inversions
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 →
@episodeyang: your algorithm is correct but it's slowed down by running array.pop(0). That's an O(n) operation in python. I modified your merge function to use two indices to keep track of where I was in each array and ran it in pypy3 and it passed. See code below: