You are viewing a single comment's thread. Return to all comments →
The description of the problem is quit terrible.
Basically, you need to implement a merge sort and add a counter.
This counter is incremented when you merge, everytime you copy from the right part of the buffer, the number of swaps will be this :
swaps += int64(mid + 1 - left)
where left is the current index you use to keep track of which values from the left buffer where copied in the array
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 description of the problem is quit terrible.
Basically, you need to implement a merge sort and add a counter.
This counter is incremented when you merge, everytime you copy from the right part of the buffer, the number of swaps will be this :
swaps += int64(mid + 1 - left)
where left is the current index you use to keep track of which values from the left buffer where copied in the array