#codingexercise
Performing inversion count on an array of unsorted positive integers.
Given an array such as {1, 20, 6, 4, 5 } the number of inversions is 5.
One way to do this is to count it by traversal with order of O(N^2)

Int GetCountInversions(List<int> A) 

{ 

Int count = 0; 

For (int I =0; I < A.Count(); i++) 

    For (int j = i+1; j < A.Count(); j++) 

       If (A[i]  > A[j]) 

            count++; 

return count; 

} 

Another way is to use merge sort where we used the merge of two sorted sub-arrays to discover the inversion count as those from individual sub arrays  and that from the merge. The inversion count from the merge is merely comes with the benefit that the position in the sorted left sub-array for an inverted element as i  contributes (mid-i) inversions.

Another way to do this would be to use a self-balancing AVL tree that keeps track of inversions for every node. The count is initialized to zero and as the elements are inserted into the AVL tree, the count is updated. The insertion operation also updates the result because the insertion requires traversal from root to leaf. The count is increased by 1 and the number of nodes in the right subtree of the current node which gives the inversions up to this element in the array from index 0 to current position. 

Node Insert(ref Node root, Node z, ref count) 
{ 
assert(z); 
z.height = -1; 
if (!root) 
     root = z; 
else if (z.data < root.data) 
     root.left = Insert(root.left, z, ref count); 
     count = count + root.right + 1 
else 
     root.right = Insert(root.right, z, ref count); 

root.height = 1 + max(height(root.left), height(root.right)); 
Balance(root); 
} 

Node Balance(Node root) 
{ 
FixHeight(root); // 1 more than left or right 
if (Bfactor(root) == 2) // Bfactor is h(right)-h(left) 
{ 
      if (Bfactor(root.right) < 0) 
           root.right = RightRotate(root.right); // returns root.right.left 
      return LeftRotate(root); 
} 
if(BFactor(root) == -2) 
{ 
      if (Bfactor(root.left) > 0) 
           root.left = LeftRotate(root.left); 
      return RightRotate(root); 
} 
return root; 
} 


Balance is based on rotation after fixing height.