This is a HackerEarth Challenge Problem.Question:  Puchi hates to carry luggage, but unfortunately he got a job to carry  the luggage of his N friends in office. Each day, one of his N  friends, gives him the luggage of a particular weight to carry. You  will be given the weight of luggage of each friend in the array  Weight, where Weighti is the weight of luggage of ith friend carried  by Puchi on ith day. It is given that all the luggages carried by  Puchi are distinct in their weights. As Prateek assigned this job to  Puchi, so for each day, he wants to know the number of days in future  when Puchi will have to carry the luggage , having weight less than  the weight of luggage of current day. Please help Prateek for the  same.Input:   The first line contains a single integer T, denoting the number of test cases. In each test case, the following input will be  present: First line contains an integer N, where N represents the  number of friends. Next N line contains N integers, where ith line  contains ith integer, which represents Weighti.Output:     Output exactly T lines. Each line contains N integer separated by a space, where ith integer represents the number of  luggage of future, which are less than the weight of luggage of the  current day.Constraints: Subtask 1:   1 <= T <= 30 1<= N <= 104 1<= Weighti <= 106Subtask 2:   1 <= T <= 10 1<= N <= 105 1<= Weighti <= 106I have used merge sort to calculate the inversions:public class Puchi_and_Luggage {static long invfreq[]=new long[1000001];    public static void main(String[] args) throws NumberFormatException, IOException {        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));             int T=Integer.parseInt(br.readLine().trim());        while(T-->0)        {          int N=Integer.parseInt(br.readLine().trim());          StringBuilder ans=new StringBuilder();          int arr[]=new int[N];          int copy[]=new int[N];          for(int i=0;i<N;i++)          {              arr[i]=Integer.parseInt(br.readLine().trim());              copy[i]=arr[i];              invfreq[arr[i]]=0l;          }          mergesort(arr,0,N-1);          for(int i=0;i<N;i++)          {            ans.append(invfreq[copy[i]]+ );          }          System.out.println(ans);        }    }    private static void mergesort(int[] arr, int i, int j) {        int mid=0;        if(i<j)        {            mid=(i+j)/2;                        mergesort(arr,i,mid);            mergesort(arr,mid+1,j);            merge(arr,i,mid,j);         }    }    private static void merge(int[] arr, int i, int mid, int j) {        int temp[]=new int[arr.length];        int l=i;        int r=j;        int m=mid+1;        int k=l;        long inv=0l;        while(l<=mid && m<=r)        {            if(arr[l]<=arr[m])            {                temp[k]=arr[l];                invfreq[temp[k]]+=inv;                k++;                l++;            }            else            {                temp[k]=arr[m];                k++;                m++;                inv++;            }        }        while(l<=mid){            temp[k]=arr[l];            invfreq[temp[k]]+=inv;            k++;            l++;        }        while(m<=r){                        temp[k]=arr[m];             k++;            m++;        }        for(int i1=i;i1<=j;i1++){            arr[i1]=temp[i1];            //System.out.print(arr[i1]+ );        }    }}But my code is giving Time Limit Exceeded for test cases with large input files.
Counting number of inversions
java;programming challenge;sorting;time limit exceeded;mergesort