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.
// Function to count the number of inversions// during the merge processfunctionmergeAndCount(arr,l,m,r){// Left subarrayletleft=[];for(leti=l;i<m+1;i++){left.push(arr[i]);}// Right subarrayletright=[];for(leti=m+1;i<r+1;i++){right.push(arr[i]);}leti=0,j=0,k=l,swaps=0;while(i<left.length&&j<right.length){if(left[i]<=right[j]){arr[k++]=left[i++];}else{arr[k++]=right[j++];swaps+=(m+1)-(l+i);}}while(i<left.length){arr[k++]=left[i++];}while(j<right.length){arr[k++]=right[j++];}returnswaps;}// Merge sort functionfunctionmergeSortAndCount(arr,l,r){// Keeps track of the inversion count at a// particular node of the recursion treeletcount=0;if(l<r){letm=Math.floor((l+r)/2);// Total inversion count = left subarray count// + right subarray count + merge count// Left subarray countcount+=mergeSortAndCount(arr,l,m);// Right subarray countcount+=mergeSortAndCount(arr,m+1,r);// Merge countcount+=mergeAndCount(arr,l,m,r);}returncount;}functioncountInversions(arr){returnmergeSortAndCount(arr,0,arr.length-1);}
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 →
JS version
Ref: https://www.geeksforgeeks.org/inversion-count-in-array-using-merge-sort/