Random commentary about C++, STL, Boost, Perl, Python, Algorithms, Problem Solving and Web Search
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.