Counting number of inversions 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 &lt;= T &lt;= 30 1&lt;= N &lt;= 104 1&lt;= Weighti &lt;= 106
  
  Subtask 2:   1 &lt;= T &lt;= 10 1&lt;= N &lt;= 105 1&lt;= Weighti &lt;= 106


I 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--&gt;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&lt;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&lt;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&lt;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&lt;=mid &amp;&amp; m&lt;=r)
        {
            if(arr[l]&lt;=arr[m])
            {
                temp[k]=arr[l];
                invfreq[temp[k]]+=inv;
                k++;
                l++;
            }
            else
            {
                temp[k]=arr[m];
                k++;
                m++;
                inv++;

            }

        }
        while(l&lt;=mid){
            temp[k]=arr[l];
            invfreq[temp[k]]+=inv;
            k++;
            l++;
        }
        while(m&lt;=r){            
            temp[k]=arr[m]; 
            k++;
            m++;
        }

        for(int i1=i;i1&lt;=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.
Short answer: creating - and garbage collecting - N arrays of size N takes some time, even if operator new[] has been tuned for exceptional performance (as is the case for Java and C#).

int temp[]=new int[arr.length];


Long answer: a detailed treatment of all the coding/performance sins inherent in the code offered for review would fill many pages. However, I'm leaving that for someone else and instead I'll focus only on the algorithmics, in a language-agnostic way.

Throwing needlessly complicated technology at a practice problem can be educational, if only to drive the lesson home that the technology in question is in fact not a good match for the problem and that other solutions require less effort. Hence, if a problem listed under ‘merge sort’ then one ought to also solve it via merge sorting, but the first call should always be the simplest solution that promises to do the job.

In this case, that simplest solution is using a Fenwick tree to count inversions. No fuss, no muss, solution (C#) accepted with 1.19 s combined time for all test files.

const int MAX_VALUE = 1000000;

for (int t = int.Parse(Console.ReadLine().Trim()); t-- &gt; 0; )
{
    int n = int.Parse(Console.ReadLine().Trim());
    var a = new int[n];

    for (int i = 0; i &lt; n; ++i)
        a[i] = int.Parse(Console.ReadLine().Trim());

    var fenwick = new int[1 + MAX_VALUE];
    var result = new int[n];

    for (int i = n - 1; i &gt;= 0; --i)
    {
        int a_i = a[i], inversions = 0;

        for (int j = a_i; j &gt; 0; j -= j &amp; -j)
            inversions += fenwick[j];

        for (int j = a_i; j &lt;= MAX_VALUE; j += j &amp; -j)
            ++fenwick[j];

        result[i] = inversions;
    }

    Console.WriteLine(string.Join(" ", result));
}


Compare this to the reams of code necessary for the merge sorting approach.

According to the problem constraints, values can go ten times as high as indices (limit 10^6 instead of 10^5). This makes the Fenwick ten times as big as the biggest input array, increasing the average path lengths for the Fenwicking from not quite 9.5 to not quite 11.5. However, for small ranges such as these this inefficiency is negligible - the code is more than fast enough already. 

For details on Fenwick trees see the Wikipedia article on Fenwicks and the related practice section on HackerEarth (which includes a tutorial; it's in the Data Structures section which you're supposed to work through before starting with Algorithms). As regards determining the average iteration counts for the Fenwick loops, I'd recommend doing a bit of Fenwicking with pen and paper (for a Fenwick of size 2^k it's k / 2 + 1).

As regards merge sorting: unlike Fenwicks, merge sorting does not give a flying meow about what the actual ranges of the input values are - all it does with the inputs is compare them. This makes the algorithm especially attractive when the value range diverges wildly from the value count. For example, Fenwicking 100000 longs would require sorting the inputs in order to ‘compress’ them to the range 1 to 100000, which requires O(N log N) of extra effort. 

Merge sorting requires no such preprocessing, but since it destroys the original order of the values it requires extra effort for correlating the inversion counts thus found to the original inputs (e.g. the array copy[] in the original code). Also, it makes the code quite a bit more complicated than that using a Fenwick tree, and it would get hugely more complicated if the input values weren't guaranteed to be unique whereas the Fenwick couldn't care less about uniqueness.

Coding a top-down merge sort with recursive function calls - as opposed an iterative bottom-up version with nested loops - makes it more difficult to control certain aspects (e.g. optimal splitting instead of simple halving) and it makes it even more difficult to make sorted ranges end up precisely where they're needed, instead of resorting to redundant copying of values. 

However, the recursive version has somewhat better cache locality and in any case it is more than fast enough for this problem, regardless of the redundant copying. In my benchmarks it took little more than twice as long as the simpler Fenwick and was only marginally slower than an iterative version (124 ms for 10^6 values recursive vs 110 ms iterative and 44 ms Fenwick). In a coding challenge it might pay to keep the differences in mind, but not for this simple practice problem.

Hence the only algorithmic fix required here is using a pre-allocated temp array large enough to hold the largest input. That's all.