Antonio Gulli's coding playground

How do you want the answer? If it's just the list of pairs, then we have a problem.

There could be n(n-1)/2 inversion pairs, so even just outputting the answer takes more than O(n).

Didn't know there is O(n) algorithm for inversions. What I knew was O(n log n) for inversions - modification of merge sort. Divide array into two, solve recursively, then when doing the merge part generate/count the inversions. I'm interested to hear O(n) solution for counting the inversions. Thank you.