Given an integer array **arr[]** of length **n**, the task is to find the inversion count of **arr[]**.

Two elements, **arr[i]** and **arr[j]**, form an inversion if **arr[i] > arr[j]** and **i < j**. If the array is already sorted, then the inversion count is **0**.

If an array is sorted in the reverse order, then the inversion count is the maximum.

**Example 1**

**Input:** arr[] = {2, 4, 1, 3, 5}, n = 5, **Output:** 3

**Example 2**

**Input:** arr[] = {1, 20, 6, 4, 5}, n = 5, **Output:** 5

## Solutions

### Method 1: In O(n log n) time

In this approach, we use **modified merge sort** such that every time a greater element is found in the left array, we increment the count by one and return the count at the end.

If **left[i]** is greater than **right[j]**, then there are **((mid + i) - (l + 1))** inversions because left and right subarrays are sorted, so all the remaining elements in left-subarray (right[mid+i] to right[mid]) will be greater than right[j].

##### Complexity

The time complexity of this solution is **O(n)** and space complexity is **O(n log n)**.

### Method 2: In O(n^2) time

Traverse through the array from left to right, and for each element, find the number of **smaller elements on its right** side. Add up the count of inversions for every index and print.

##### Complexity

The time complexity of this solution is **O(n)** and space complexity is **O(n^2)**.