Mergesort and couting the amount of inversions

[Jochus]

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:

 

[John Ratliff]

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).

This is not a question for comp.lang.c++ which deals with standard C++
language issues ONLY. Please find a newgrsoup dedicated to algorithms.

See http://www.parashift.com/c++-faq-lite/ for more information.

--John Ratliff