Today, I've programmed Mergesort. And it works very good :-)!
But now, the teacher said that you could use Mergesort to count the amount
of inversions.
This is what I found on the internet:
---
Note: Merge Sort can be slightly modified to count inversion index (i.e.
bubble sort swaps) in O(n log n) time. When the right partition goes in
first in Merge step, that means all the remaining items in left partition <
first element in right partition (i.e. you have to swap with all of them).
---
Can someboy give me some information about that sentence? I don't really
understand the meaning of it...