# 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 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;
String []str;
ans=new int[t];
for(i=0;i<t;++i)
{
noi=0;
arr=new int[n];
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);
}
}

• Can you provide the test files? Sep 26, 2015 at 4:43

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.
• You are a life saver.But there is one problem now. Sep 26, 2015 at 5:29
• For some reason which only god knows, Now my code is failing 6 out of 13 test cases. Sep 26, 2015 at 5:29
• Got it, It was due to overflow, noi variable must be long. Sep 26, 2015 at 5:33
• Brilliant observation.Keep up the good work. Sep 26, 2015 at 5:34
• I thank you a lot.However,I still require your help. Sep 26, 2015 at 17:55

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
}

• I preallocated everything but nothing changes. Still timeout. Sep 25, 2015 at 19:07
• Instead of using System.arraycopy I also tried other methods but to no avail. Sep 25, 2015 at 19:12