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.

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

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

ReplyDelete