How to: array inversion count

Inversion Count for an array indicates – how far (or close) the array is from being sorted. If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum. 

Formal solution to solve is:
Given is an array A of N integers. Inversion is a pair of indexes (P, Q) such that P < Q and A[Q] < A[P].

Write a function

class Solution { public int array_inversion_count(int[] A); }

which computes the number of inversions in A, or returns -1 if such number exceeds 1,000,000,000.

Assume that:

        N is an integer within the range [0..100,000];
        each element of array A is an integer within the range [-2,147,483,648..2,147,483,647].

For example, in the following array

    A[0] = -1 A[1] = 6 A[2] = 3
    A[3] =  4 A[4] = 7 A[5] = 4

there are four inversions:

      (1,2)  (1,3)  (1,5)  (4,5)

so the function should return 4.

Complexity:

        expected worst-case time complexity is O(N*log(N));
        expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).


import java.math.*;
class Solution {
public int array_inversion_count ( int[] A ) {
// write your code here

int n = A.length;
int counter = 0;
for(int p = 0; p < n - 1; p++) 
   { 
      for(int q = p+1; q < n; q++) 
      { 
         if( A[p] > A[q] ) counter++;
      }
   }
   return counter;
  }
}