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.
The key here is, "Whenever we pick a number from the right array because it is smaller than the left array, then we have to add to the inversions. How many? The length of the remainder of the left array."
So for example, let us recombine these two arrays step by step by comparing the smallest elements of each:
123/121<=1->23/122>1->23/2
(1 is less than 2 and 3 from the left array remainder. We add 2 (the length of the left array remainder). INV += 2; INV is now 3)
2<=2->3/23<2->3
(2 is less than 3 from the left array remainder. We add 1 (the length of the left array remainder). INV += 1; INV is now 4)
3 -> done
count+=mid+1-i;
This adds the length of the remainder of the left array to the count.
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 →
The key here is, "Whenever we pick a number from the right array because it is smaller than the left array, then we have to add to the inversions. How many? The length of the remainder of the left array." So for example, let us recombine these two arrays step by step by comparing the smallest elements of each:
(1 is less than 2 and 3 from the left array remainder. We add 2 (the length of the left array remainder). INV += 2; INV is now 3)
(2 is less than 3 from the left array remainder. We add 1 (the length of the left array remainder). INV += 1; INV is now 4)
3 -> done
This adds the length of the remainder of the left array to the count.