find total number of (i,j) pairs in array such that i<j and a[i]>a[j]

Question

As mentioned in the question ,need to find total number of (i,j) pairs in array such that

(1) **i<j** 
(2) **a[i]>a[j]**

where i and j are indices of the array . There are no space constraints .

My question is

 1) Is there any approach which takes less than O(N^2) time?
 2) if so what is least complexity ?
 3) How do we prove that ? 

I hope i'm clear with the question .

My approach is as follows

One way of doing the question is using brute fore which takes O(N^2) time .

But I think that there should be a better optimised solution to this question at-least O(NlogN) sollution .The reason for my intuition is as follows

Intuition 1) For sorting an array in ascending order conditions we have are : for i<j , a[i]<a[j] which is similar to my question . I also read that sorting has lower bound of Omega(n log n) . So my question should also have Omega(n log n) . I may be completely wrong if so please correct me .

My second intuition is:

Suppose we have an array of elements as follows : 4,9,7,3,2,1,8,12

we calculate above condition i<j , a[i]>a[j] for element 4 ,as i=0 points to 4 ,the possible values for j are 3,4,5 .since a[0]>a[3],a[0]>a[4],a[0]>a[5] ,so my total no of (i,j) pairs for now is 3 . Next time when I increment i(index) to 1,the possibles values of j are 2,3,4,5,6 . But we should use the fact that when i=0 (when a[i]=4) we have computed 3 elements less than a[i=0] which is in turn less than a[i=1] , so i will not compare 9 with 3,2,1 (To remove unnecessary computations ).If we can remove unnecessary computations then we can reduce complexity to something less than O(N^2) or else no solution less than O(N^2) exists.But if solution exists then how do we do that.I tried making graph but my efforts are futile .

Approach 1)In-order to obtain O(nlogn) complexity I think we need to tweak around quick sort or merge sort to get solution but problem here is, if we sort the array we loose the actual positions of elements.

Approach 2)In-order to get solution in O(NlogN) time I think using tree we may get the optimised sollution . I didn't get any clue.

Approach 3)If there exists any O(N) time algorithm it should be with hashing . But in this case simple hashing doest work .

So please let me know which of the above intuitions or approaches are correct (If correct which approach will lead to optimised sollution and how).

Answer 1

Such pairs are called number of inversions in an array. It is one measure of how close the array is to being sorted. You can modify merge sort to efficiently count the number of inversions in O(nlogn) time. Refer to this for details.

Answer 2

You can count inverted pairs with the algorithm, similar to merge sort, as explained here.

The idea is to merge sort the array while counting, how many inversions were changed on each step.

---

A different approach is to use an order-statistics tree. You sequentially insert elements of the array into this tree, and after each insertion see, how many elements, preceding the inserted element, are larger than it.

An alternative to order-statistics tree is Indexable skiplist.

---

Both algorithms have O(N log N) time complexity.

To get approximate number of inversions, O(N) time complexity is possible with some limitations. We can modify Bucket sort in the same manner merge sort was modified.

On "scatter" phase of Bucket sort we should estimate number of elements in buckets for larger elements, while inserting element at the end of some bucket (elements in each bucket remain in original order).

On "sort" phase of Bucket sort we should modify (in the same way) sorting algorithm (insertion sort, most likely). While inserting the element into its proper place, we should count over how many other elements it jumped.

As for limitations, this algorithm works only with numbers (or with objects, easily convertible to numbers), and we should know in advance how these numbers are distributed. So, if we have an array of uniformly distributed integers, this algorithm should work properly.