Tuesday, April 12, 2011

Inversion pairs

Given an array of n integers find all the inversion pairs in O(n).


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

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