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.
(By Merge_and_CountSplitInv():
- :param left_half: sorted list C
- :param right_half: sorted list D
- :return: sorted list B (length n) and the number of split
inversions)
defMerge_and_CountSplitInv(left_half,right_half):i=0j=0splitInv=0B=[]whilei<len(left_half)andj<len(right_half):ifleft_half[i]<=right_half[j]:B.append(left_half[i])i+=1else:B.append(right_half[j])j+=1splitInv+=(len(left_half)-i)B+=left_half[i:]B+=right_half[j:]returnB,splitInvdefSort_and_CountInv(A):# base caseiflen(A)<2:returnA,0# divide the list into twomid=len(A)// 2left=A[:mid]#recursivelysortfirsthalfofAright=A[mid:]#recursivelysortsecondhalfofAx,leftInv=Sort_and_CountInv(left)y,rightInv=Sort_and_CountInv(right)z,splitInv=Merge_and_CountSplitInv(x,y)returnz,leftInv+rightInv+splitInv
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 →
So true! Thanks a lot :)
Here is my code is you feel like reviewing it:
(By Merge_and_CountSplitInv(): - :param left_half: sorted list C - :param right_half: sorted list D - :return: sorted list B (length n) and the number of split inversions)