java - Inversion Count using Divide And Conquer -

i trying implement program counts number of inversions, not working big input size(100,000).

the unsorted numbers picked txt file. program works small input size 10 or 15 or 20.

but when copy input link:http://spark-public.s3.amazonaws.com/algo1/programming_prob/integerarray.txt program keeps running several seconds without producing output.

i have used divide , conquer algorithm based on merge sort , implemented in bluej.

here code.

import java.util.*; import java.io.*; class inversion {  private static linkedlist<integer>arr;  private static scanner s;  private static long count=0;  public static void count_inv(int low,int high)  {      if(high<=low)       return ;      else      {          int mid= low + (high-low)/2;          count_inv(low,mid);          count_inv(mid+1,high);          split_inv(low,high);       }  }  public static void split_inv(int low,int high)  {      int mid=low+ (high-low)/2;      int i=low,j=mid+1;      int k=0;      int []aa=new int[high-low+1];      while(i<=mid&&j<=high)      {          if(arr.get(i)<=arr.get(j))           aa[k++]=arr.get(i++);          else {count+=mid-i+1; aa[k++]=arr.get(j++);}      }      while(i<=mid)       aa[k++]=arr.get(i++);      while(j<=high)       aa[k++]=arr.get(j++);      for(int e:aa)       arr.set(low++,e);   }  public static void main(string []args)throws ioexception  {   bufferedreader br=new bufferedreader(new filereader("jj.txt"));   arr=new linkedlist<integer>();   string s="";   while((s=br.readline())!=null)    arr.add(integer.parseint(s));                   count_inv(0,arr.size()-1);   system.out.println("the number of inversions "+count);     } } 

i think problem might using linkedlist.

this have o(n) access time random access.

you o(nlogn) accesses, overall time o(n^2logn).

try using normal array, or other data structure o(1) access time such arraylist.