Inversion count algorithm

Question

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<t;++i)
        {
         noi=0; 
         n=Integer.parseInt(br.readLine());   
         arr=new int[n];
         str=br.readLine().split(" ");
         for(k=0;k<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>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<=mid&&k<=r)
        {
            if(arr[j]<=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);        
    }    
}

Answer 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:

1. Don't use lower case L as a variable name. It looks too similar to the digit 1.
2. 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
3. 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.

Answer 2

When in doubt, profile.

That said, I may speculate that most of the time is wasted in a final System.arraycopy(arr2,0,arr,l,r-l+1); (and maybe in new int[r-l+1]; I don't know how Java does the allocation).

I recommend to preallocate a scratch area - as large as the data array - at the beginning; sort into the scratch area, and merge back into the source:

    merge_sort(int[] src, int dst[], int l, int r) {
        int mid = l + (r - l)/2;
        merge_sort(src, dst, l, mid);
        merge_sort(src, dst, mid + 1, r);
        // at this moment, subarrays in dst are sorted
        merge(dst, src, l, mid, r); // Note that merge goes dst -> src
    }