Inversion count algorithm I implemented the inversion count algorithm using the merge sort approach for this question.

The question begins with a number t = number of test cases and then for each test case you input size of array and then the array entries.

For each test case we have to find the number of inversions = number of shifts made by insertion sort algorithm.

I was surprised to see that only 2 test case passed out of 13 and rest all time out. Can somebody suggest a way I should go about speeding up my code?

Kindly ignore the OOP principles for the time being.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class So {
    private static BufferedReader br;
    private static int n,index,t,noi=0;       
    private static int []arr;    
    private static int []ans;  
    public static void main(String[] args)throws IOException {        
        int i,k=1;int s,st,j;
        br=new BufferedReader(new InputStreamReader(System.in));
        String []str; 
        t=Integer.parseInt(br.readLine());
        ans=new int[t];
        for(i=0;i&lt;t;++i)
        {
         noi=0; 
         n=Integer.parseInt(br.readLine());   
         arr=new int[n];
         str=br.readLine().split(" ");
         for(k=0;k&lt;n;++k)
          arr[k]=Integer.parseInt(str[k]);
         ms(0,n-1);         
         ans[i]=noi;
        }
        for(int e:ans)
         System.out.println(e);
    }
    public static void ms(int l,int r)
    {
        if(r-l&gt;0)
        {
            int mid=(l+r)/2;
            ms(0,mid);
            ms(mid+1,r);
            merge(l,r);
        }
    }
    public static void merge(int l,int r)
    {
        int []arr2=new int[r-l+1];
        int j,k,mid=(l+r)/2;
        k=mid+1;int i=0;
        j=l;
        while(j&lt;=mid&amp;&amp;k&lt;=r)
        {
            if(arr[j]&lt;=arr[k])
             arr2[i++]=arr[j++];
            else {arr2[i++]=arr[k++];noi+=mid-j+1;}
        }        
        System.arraycopy(arr,j,arr2,i,mid-j+1);        
        System.arraycopy(arr,k,arr2,i,r-k+1);
        System.arraycopy(arr2,0,arr,l,r-l+1);        
    }    
}
The timeout is caused by a bug is in the ms method.  ms(0,mid)  should be ms(l, mid).

A few comments on the code itself:


Don't use lower case L as a variable name.  It looks too similar to the digit 1.
Don't use static variables to communicate between your methods.  It makes the code harder to test and you risk bugs due to crosstalk between different invocations of the method.  In this case, for example, ms and merge should just return the number of shifts instead of incrementing static counter noi
Better separation of input parsing from actual computation.  You should have a method long countingMergeSort(int[] ary).  That would make it easier for you to test your code.