Last Updated on June 17, 2022 by Ria Pathak

### Concepts Used

Sorting

### Difficulty Level

Hard

### Problem Statement (Simplified):

Find number of pairs such that

`a[i]`

>`a[j]`

and`i`

<`j`

.

#### Test Case

```
Input:
1
5
10 50 20 40 30
Output:
4
Explanation:
Such required pairs are (50,20),(50,40),(50,30) and (40,30). So, 4 is our answer.
```

**See original problem statement here**

### Solving Approach :

**Bruteforce Approach**:

We can count for each element, such a number of elements on it’s right which are smaller to the current element, this gives us the number of inversions for the current element, hence it can be calculated for all elements in the array. But this approach takes O(n

^{2}) time, which is not efficient for larger array sizes. Hence we can solve it more efficiently by following approach which takes`O(n\times{log(n)})`

time.

**Efficient Approach**:

1) We can count the total number of inversions during sorting array using

.Merge Sort Algorithm

2) In the merge sort algorithm when we merge two halves of the array, we copy elements from two halves into the auxiliary array. If the element from the left half is greater than the current right half element, that is also our one inversion as the left element has a lower index than the element in the right half.

3) Total number of inversions in above step would be`(mid-1)`

because left and right subarrays are sorted, so all the remaining elements in left-subarray (a[i+1], a[i+2] … a[mid]) will be greater than a[j].

So we count all these inversions and print them as the answer.

### Example

As we saw in, the efficient approach we can count inversions during the merge sort itself. Let array

`A`

be,

Drawing recursion tree for given array, explains a lot about it,

Here, while merging, we can see

`right`

`child`

have a inversion`(40,30)`

, we add this to our inversion count and move to next step.Here again, while merging on the

`left`

`child`

, we observe an inversion`(50,20)`

, we add this to our inversion count and move further.

In this step, we see that right

`child`

have two elements which are less than last element of`left`

`child`

, hence both will be counted as inversions`(50,30),(50,40)`

. We count both and move further.

Now, we have our array sorted, which means there exists no inversion anymore, so we print count and terminate the program.

### Solutions

#includelong long merge(int arr[], int temp[], int left, int mid, int right){ int i, j, k; long long inv_count = 0; i = left; j = mid; k = left; while ((i <= mid - 1) && (j <= right)) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; inv_count = inv_count + (mid - i); } } while (i <= mid - 1) temp[k++] = arr[i++]; while (j <= right) temp[k++] = arr[j++]; for (i = left; i <= right; i++) arr[i] = temp[i]; return inv_count; } long long _mergeSort(int arr[], int temp[], int left, int right){ int mid; long long inv_count = 0; if (right > left) { mid = (right + left) / 2; inv_count = _mergeSort(arr, temp, left, mid); inv_count += _mergeSort(arr, temp, mid + 1, right); inv_count += merge(arr, temp, left, mid + 1, right); } return inv_count; } long long mergeSort(int arr[], int array_size){ int temp[array_size]; return _mergeSort(arr, temp, 0, array_size - 1); } int main() { int test; scanf("%d",&test); while(test--){ int n; scanf("%d",&n); int arr[n]; for(int i=0; i

#includeusing namespace std; long long merge(int arr[], int temp[], int left, int mid, int right){ int i, j, k; long long inv_count = 0; i = left; j = mid; k = left; while ((i <= mid - 1) && (j <= right)) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; inv_count = inv_count + (mid - i); } } while (i <= mid - 1) temp[k++] = arr[i++]; while (j <= right) temp[k++] = arr[j++]; for (i = left; i <= right; i++) arr[i] = temp[i]; return inv_count; } long long _mergeSort(int arr[], int temp[], int left, int right){ int mid; long long inv_count = 0; if (right > left) { mid = (right + left) / 2; inv_count = _mergeSort(arr, temp, left, mid); inv_count += _mergeSort(arr, temp, mid + 1, right); inv_count += merge(arr, temp, left, mid + 1, right); } return inv_count; } long long mergeSort(int arr[], int array_size){ int temp[array_size]; return _mergeSort(arr, temp, 0, array_size - 1); } int main() { int test; cin>>test; while(test--){ int n; cin>>n; int arr[n]; for(int i=0; i >arr[i]; cout<

import java.util.*; import java.io.*; class Test { static long mergeSort(int arr[], int array_size) { int temp[] = new int[array_size]; return _mergeSort(arr, temp, 0, array_size - 1); } static long _mergeSort(int arr[], int temp[], int left, int right) { int mid; long inv_count = 0; if (right > left) { mid = (right + left) / 2; inv_count = _mergeSort(arr, temp, left, mid); inv_count += _mergeSort(arr, temp, mid + 1, right); inv_count += merge(arr, temp, left, mid + 1, right); } return inv_count; } static long merge(int arr[], int temp[], int left, int mid, int right) { int i, j, k; long inv_count = 0; i = left; j = mid; k = left; while ((i <= mid - 1) && (j <= right)) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; inv_count = inv_count + (mid - i); } } while (i <= mid - 1) temp[k++] = arr[i++]; while (j <= right) temp[k++] = arr[j++]; for (i = left; i <= right; i++) arr[i] = temp[i]; return inv_count; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int t=sc.nextInt(); while(t-->0) { int n = sc.nextInt(); int arr[] =new int[n]; for(int i=0;i

**Space Complexity**

O(

`n`

) for an auxiliary array of the same size as our input array.

[forminator_quiz id="1230"]

This article tried to discuss the concept of **Sorting**. Hope this blog helps you understand the concept of Sorting. To practice more problems you can check out MYCODE|competitive programming