title: How to find the number of inversions in an array ?
body: <blockquote>
  <p><strong>Possible Duplicate:</strong><br />
  <a href="https://stackoverflow.com/questions/337664/counting-inversions-in-an-array">Counting inversions in an array</a></p>
  </blockquote>
  
  <p>This is an <a href="http://www.glassdoor.com/Interview/Phone-Interview-i-Find-the-number-of-inversions-in-an-array-describe-and-code-ii-Find-collinear-points-in-a-given-set-QTN_129352.htm" rel="noreferrer">phone interview question</a>: &quot;Find the number of inversions in an array&quot;. I guess they mean O(N<em>log N) solution. I believe it cannot be better than O(N</em>log N) since this is the sorting complexity.</p>
  <p>The answers to a <a href="https://stackoverflow.com/questions/337664/counting-inversions-in-an-array">similar question</a> can be summarized as follows:</p>
  <ol>
  <li><p>Calculate half the distance the elements should be moved to sort the array : copy the array and sort the copy. For each element of the original array <code>a[i]</code> find it's position <code>j</code> in the sorted copy (binary search) and sum the halves the distances <code>abs(i - j)/2</code>.</p>
  </li>
  <li><p>Modify <code>merge sort</code> : modify <code>merge</code> to count inversions between two sorted arrays and run regular <code>merge sort</code> with that modified <code>merge</code>.</p>
  <p>Does it make sense ? Are there other (maybe simpler) solutions ? Isn't it too hard for a phone interview ?</p>
  </li>
  </ol>