Given an array of integers A[ ], if i < j and A[i] > A[j] then the pair (i, j) is called an inversion of A[]. Write a program to find the total number of inversion count in A[].

Problem Note

  • Inversion Count for an array indicates – how close the array is from being sorted.
  • If the array is already sorted then the inversion count is 0.
  • we are assuming that all elements are unique.
  • If the array is sorted in reverse order that inversion count is the maximum.

Example 1

Input: A[] = [4, 1, 3, 2] 
Output: 4 
Explanation: There are four inversions:(4, 1),(4, 3),(4, 2) and (3, 2). 

Example 2

Input: A[] = [4, 3, 2, 1] 
Output: 6 
Explanation: There are three inversions:(4, 3),(4, 2),(4, 1) ,(3, 2),(3, 1) and (2, 1). 

Example 3

Input: A[] = [1, 2, 3, 4] 
Output: 0 
Explanation: Array is already sorted.