2
\$\begingroup\$

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);        
    }    
}
\$\endgroup\$
  • \$\begingroup\$ Can you provide the test files? \$\endgroup\$ – coderodde Sep 26 '15 at 4:43
3
\$\begingroup\$

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

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
    }
\$\endgroup\$
  • \$\begingroup\$ I preallocated everything but nothing changes. Still timeout. \$\endgroup\$ – Sumeet Sep 25 '15 at 19:07
  • \$\begingroup\$ Instead of using System.arraycopy I also tried other methods but to no avail. \$\endgroup\$ – Sumeet Sep 25 '15 at 19:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.