title: How do I find the number of inversions in an array?
body: <p>Basically I'm trying to write an algorithm in Java to determine the number of pairs in an array that are out of order. So if we take i and j and j is in a higher position in an array than i but A[i] > A[j] then it counts those two numbers as an inversion. Currently this is what I have:</p>
  
  <pre><code>for(int i = 0; i&lt;n-1; i++){
      if (A[i] &gt; A[i+1]){
          k++;
  </code></pre>
  
  <p>What this does is only compared the pairs that are right next to eachother so now I'm trying to modify this to find any two numbers in the array where the lower position is a higher value than the number in the higher position. I know how to do something like that but I want the run time to be (n+k) where n is the length of the array and k is the number of inversions in the array. </p>
  
  <p>EDIT: Here's my attempt to implement insertion sort:</p>
  
  <pre><code>int k = 0;
  int [] A = {5, 4, 3, 2, 1};
  int n = A.length;
  for(int i = 1; i &lt; n; i++){
      int temp = A[i];
      int j;
      for (j = i - 1; j &gt;=0 &amp;&amp; temp &lt; A[j]; j--){
          A[j + 1] = A[j];
      A[j + 1] = A[j];
          k++;
  </code></pre>
  
  <p>k is supposed to be keep track of how many inversions. For the array 5, 4, 3, 2, 1 the number I get returned is 6. Is that right? </p>