title: Counting inversions in an array
body: <p>I'm designing an algorithm to do the following: Given array <code>A[1... n]</code>, for every <code>i &lt; j</code>, find all inversion pairs such that <code>A[i] &gt; A[j]</code>. I'm using merge sort and copying array A to array B and then comparing the two arrays, but I'm having a difficult time seeing how I can use this to find the number of inversions. Any hints or help would be greatly appreciated.</p>