title: Find the number of inversions
body: <p>Following is an algorithm which is supposed to find number of inversions in an array using merge sort. It produces false output and although it is very simple, I can't see what's wrong with it. Can you please help me out?</p>
  
  <p>For example, for input 1 3 3 1 2, that is, for perm. (3 1 2) it produces 39994, instead of 2.</p>
  
  <pre><code>/* *
   * INPUT:
   * 1. t : number of test cases; t test cases follow
   * 2. n : number of elements to consider in each test case
   * 3. ar[i] : n numbers, elements of considered array
   * */
  
  import java.util.*;
  
  public class Inversions {
  
      // Merges arrays left[] and right[] into ar[], returns number of
      // inversions found in the process
      public static long merge(long[] arr, long[] left, long[] right) {
          int i = 0, j = 0;
          long count = 0;
          while (i &lt; left.length || j &lt; right.length) {
              if (i == left.length) {
                  arr[i+j] = right[j];
                  j++;
              } else if (j == right.length) {
                  arr[i+j] = left[i];
                  i++;
              } else if (left[i] &lt;= right[j]) {
                  arr[i+j] = left[i];
                  i++;                
              } else {
                  arr[i+j] = right[j];
                  // # inv. is curr. size of left array
                  count += left.length-i;
                  j++;
              }
          }
          return count;
      }
  
      // Traditional merge sort on arr[], returns number of inversions
      public static long invCount(long[] arr) {
          if (arr.length &lt; 2)
              return 0;
  
          int m = (arr.length + 1) / 2;
          long left[] = Arrays.copyOfRange(arr, 0, m);
          long right[] = Arrays.copyOfRange(arr, m, arr.length);
  
          return invCount(left) + invCount(right) + merge(arr, left, right);
      }
  
      public static void main (String args[]) {
          int t, n;
          long[] ar = new long[20000];
          Scanner sc = new Scanner(System.in);
          t = sc.nextInt();
          while(t-- &gt; 0) {
              n = sc.nextInt();
              for(int i = 0; i &lt; n; i++) {
                  ar[i] = sc.nextLong();
              }
              System.out.println(invCount(ar));
          }
      }
  }
  </code></pre>
  
  <p>I know I am not the first one to ask similar question. I can find the correct algorithm. I am just curious what is wrong with this one.</p>
  
  <p>Thank you!</p>