Merge sorting for solving a task

Question

I have an ArrayList with size of order 10^5. I want to count the pairs of numbers in the line, Pi and Pj, where that Pi is ahead of Pj in the line and Pi has a larger value than Pj.

CODE

public void sort(ArrayList<Integer> finalarray, int size)
        {   
            if(finalarray.size()<2) return ;

            ArrayList<Integer> right = new ArrayList<>();
            ArrayList<Integer> left = new ArrayList<>();
            int  mid = finalarray.size()/2;
            for(int i=0;i<mid;i++) left.add(finalarray.get(i));
            for(int j=mid;j<size;j++) right.add(finalarray.get(j));

            sort(left, left.size());
            sort(right, right.size());

            int l=0, r=0 , m =0;
            int temp=-1;
            while(l< left.size() && r< right.size())
            {
                  if(left.get(l)> right.get(r))
                  {
                      finalarray.set(m, right.get(r));
                     if(temp!=l)
                      answer+=r+1;
                     if( temp==l)
                         answer++;
                      r++;

                      temp=l;
                  }
                  else
                  {
                     finalarray.set(m, left.get(l));
                      l++;
                  }
                  m++;
            }
            while(l< left.size())
            {
                finalarray.set(m, left.get(l));
                 l++;
                 m++;
                 answer+=right.size();
            }
            while(r< right.size())
            {   
                finalarray.set(m, right.get(r));
                 r++;
                 m++;
            }
}

Example: Array: 1, 2, 4, 7, 5, 3
Answer: 4
(4 and 3),(7 and 5),(7 and 3),(5 and 3).
I'm using merge sort for this but I'm not getting the correct answer.
Please explain what I'm doing wrong.

Answer 1

Having a quick look at your code I presume that these lines are what gives you the wrong results:

if (temp!=l)
    answer+=r+1;`

I do not see what this is there for. If you remove it you will get the correct result.

However, I think that merge sort is not suitable to solve this problem. Have a look at this example:

For the list 5 4 3 4 the correct answer would be 4. Now lets see, what merge sort would do to this list considering your approach:

5 4 | 3 4 result 0

5 | 4 | 3 | 4 result 0

4 5 | 3 4 result 1

3 || 4 5 | 4 result 2

3 4 || 5 | 4 result 2

3 4 4 || 5 | result 3

3 4 4 5 || | result 3

Now if you think about this, merge sort does have a complexity of n*log n, so we do not look at all pairs.