title: Number of Inversion Count in an array. Using Merge Sort
body: <p>For those how not know about inversion.</p>
  
  <p>Inversion-</p>
  
  <p>Given an array A of N integers, an inversion of the array is defined as any pair of indexes (i,j) such that i &lt; j and A[i] > A[j].</p>
  
  <p>Inshort:</p>
  
  <p><strong>{inv}(A) =    {(A(i),A(j)),  i &lt; j { and } A(i) > A(j)}</strong></p>
  
  <p>For example, the array a={2,3,1,5,4} has three inversions: (1,3), (2,3), (4,5), for the pairs of entries (2,1), (3,1), (5,4).</p>
  
  <p>Total inversion count = 3.</p>
  
  <p>Well, I tried to solve this question by utilizing the standard merge sort.
  Here is how I think it works.</p>
  
  <p>Assume that at some stage, partA and partb of your merge sort is </p>
  
  <p>partA- [1,2,3].</p>
  
  <p>partB- [4,5]</p>
  
  <p>Now, Let X be the element of the first array, partA. Y be for second array, partB.</p>
  
  <p>If X is copied to output array(i.e if X &lt; Y) - Then we have no Inversion.</p>
  
  <p>Else If Y is copied to output array(i.e if X > Y). 
  Then we have Inversion count = count + mid - i+1. (i being the position of that element). As it is sorted in increasing order, all the elements at position j > i, X[j] > Y.</p>
  
  <p>Here's the code further details.</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;vector&gt;
  using namespace std;
  
  vector&lt;int&gt; a;
  vector&lt;int&gt; c;
  void merge(int low, int high, int mid);
  void mergesort(int low, int high)
  {
   int mid;
   if (low &lt; high)
   {
       mid=(low+high)/2;
       mergesort(low,mid);
       mergesort(mid+1,high);
       merge(low,high,mid);
   }
  return ;
  }
  
  int count ; //to store the inversion count
  void merge(int low, int high, int mid)
  {
  int i, j, k;
  i = low;
  k = low;
  j = mid + 1;
  // standard merging from merge sort
  while (i &lt;= mid &amp;&amp; j &lt;= high)
  {
      if (a[i] &lt; a[j])
      {
          c[k] = a[i];
          k++;
          i++;
      }
      else
      {
          c[k] = a[j];
          k++;
           j++;
        //   cout&lt;&lt;a[i]&lt;&lt;" "&lt;&lt;mid&lt;&lt;" "&lt;&lt;i&lt;&lt;"\n";
           count += mid - i+1; // This is where the trick occurs, if X &gt; Y,
           //eg. in [3, 4, 5] and [1,2]
           //if(3&gt;1) then 4,5 is obviously greater then 1, thus making count as mid - i+1              
       }
   }
  while (i &lt;= mid)
  {
      c[k] = a[i];
      k++;
      i++;
  }
  while (j &lt;= high)
  {
      c[k] = a[j];
      k++;
      j++;
  }
  for (i = low; i &lt; k; i++)
  {
      a[i] = c[i];
   }
  }
  int main()
  {
  //int a[20], i, b[20];
  int T;
  cin&gt;&gt;T;
  while(T--){
      //cout&lt;&lt;"enter  the elements\n";
      int N;
      cin&gt;&gt;N;
      count =0;
      a.clear(); a.resize(N);
      c.clear(); c.resize(N);
      for (int i = 0; i &lt; N; i++)
      {
          cin&gt;&gt;a[i];
      }
      mergesort(0, N-1);
  
      cout&lt;&lt;count&lt;&lt;"\n";
  }
  }
  </code></pre>
  
  <p>OK, Now coming to my doubt, I believe that the above implemented logic is legit enough to solve the number of inversions, but for some strange reason its not, I'm not sure whats causing WA here. </p>
  
  <p>I'm stuck at this for some time, not able to figure it out.
  It's not a homework Question, its just that I see no wrong with the logic and the code still doesn't work, what may be the possible reason? Help!.</p>
  
  <p>Ideone Link - <a href="https://ideone.com/nmvl7i" rel="nofollow">https://ideone.com/nmvl7i</a></p>
  
  <p>Question on Spoj - <a href="http://www.spoj.com/problems/INVCNT/" rel="nofollow">http://www.spoj.com/problems/INVCNT/</a></p>
  
  <p>Note: The first two test cases are working fine, While submitting I'm getting WA.</p>