[Java] Count out of order pairs in array

Given an array of unique integers, count all out of order pairs. A pair of elements is out of order if its position in the array is less than the position of the other element, but its value is bigger.

In short, count the pairs that have the first element bigger than the second, in the order that the elements appear.

A first attempt to solve this problem in complexity better than O(N^2) gave a O(N^2) solution due to a data structure limitation.

The idea was to create an empty ArrayList, then pick each element from the input array and find with binary search its position in the list. We then insert the element in the correct position and count how many elements are in the list after it, those are all elements that paired with us are out of place.

This is true since it's the first time we encounter this element, however there are other elements we saw before that are AFTER us, meaning in the initial array they appeared BEFORE us, and therefore make a pair with us of out of order elements.

The issue is that ArrayList method add(position, element) has O(N) complexity since all elements AFTER the position where we insert must be shifted one position to the right.

Using LinkedList would solve this, but cost us O(N) when binary searching as get(index) means we scan the list to get the element in the given position.

I do not know of a data structure that offers both in constant time.

The approach however is not far from the actual O(N logN) solution as we're basically sorting the input and counting these out of order pairs.

We can therefore just do that, run mergesort and when we merge left and right portions (which are sorted), for each element on the left which is bigger than the current element on the right, we consider ALL element from the END of the left portion back to the current one to be part of a pair of out of place elements.

We are indeed "moving" those elements from the left to the right side. Since each portion was sorted at a previous step, if the current element on the left is bigger than the current element on the right, also all elements AFTER him will be, so ALL of them form a pair with the right element.

This is exactly the logic applied in the first approach, but now we have indeed O(N logN) complexity at the cost of extra O(N) space.

You can check my implementation of both approaches in countOutOfOrderElements and countOutOfOrderElementsMergeSort on my Gist along with some tests in CountOutOfOrderElementsJTests. I also use an IntWrapper class in order to track this count during the mergesort recursion.