Count Inversions in an array

This question is asked from me in Goldman Sachs round 2.

This is the implementation of the Merge Sort Algorithm,

https://www.geeksforgeeks.org/counting-inversions/

Input: arr[] = {8, 4, 2, 1}
Output: 6

Explanation: Given array has six inversions:
(8, 4), (4, 2), (8, 2), (8, 1), (4, 1), (2, 1).


Input: arr[] = {3, 1, 2}
Output: 2

Explanation: Given array has two inversions:
(3, 1), (3, 2)

We need to calculate the inversions in the array,

if(ar[i]>ar[j]) && i<j.

Here we are simply doing the merge sort where while merging we are checking if (ar[i]>ar[j]) && i<j then increment the count of inversion,

also if say 2 arrays are there like {3,27,38,43} and {9,10,82} here 27 > 9 So, the total inversion is all elements right to 27 including 27 for an element 9 because if 27>9 then all the elements right to it also must be greater than 27 as both of the 2 arrays are sorted.

Here the sample code for the same.

package com.interview;public class Solution {public static void main(String[] args) {int arr[] = {38, 27, 43, 3, 9, 82, 10};int count= sort(arr, 0, arr.length - 1);System.out.println(count);for (int i : arr)System.out.print(i + " ");}public static int sort(int arr[], int left, int right) {int count = 0;if (left < right) {int mid = left + (right - left) / 2;count += sort(arr, left, mid);count += sort(arr, mid + 1, right);count += merge(arr, left, mid, right);}return count;}public static int merge(int[] arr, int left, int mid, int right) {int inversion = 0;int size1 = mid - left + 1;int size2 = right - mid;int leftArr[] = new int[size1];int rightArr[] = new int[size2];for (int i = 0; i < size1; i++)leftArr[i] = arr[i + left];for (int j = 0; j < size2; j++)rightArr[j] = arr[j + 1 + mid];int k = left;int i = 0, j = 0;while (i < size1 && j < size2) {if (leftArr[i] <= rightArr[j]) {arr[k] = leftArr[i];i++;} else {arr[k] = rightArr[j];j++;inversion += (mid + 1) - (left + i);}k++;}while (i < size1) {arr[k] = leftArr[i];k++;i++;}while (j < size2) {arr[k] = rightArr[j];k++;j++;}return inversion;}}

Happy Coding!!