[Gfg] Number of inversions in an array

Problem: Find the number of pairs (i, j) of an array A indices with i < j and A[i] > A[j].

Example:

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[] = {1, 20, 6, 4, 5}
Output: 5
Explanation: Given array has five inversions: (20, 6), (20, 4), (20, 5), (6, 4), (6, 5). 

Approach: We can use brute force approach using two loops where we go to every index 'i' and count number of indices on its right (i +1... n) where arr[i] > arr[j] where j = i + 1 ... n. This approach will work but is time consuming (O(n^2)).

We can use merge sort here, basically we can take advantage of merge process. Whenever we see there is an element in the left subarray (left...mid) say leftArr[i] which is greater than element in right subarray (mid + 1...right) say rightArr[j] then we can easily say we will get mid - i + 1 inversions right?

This is because both the arrays are sorted and if there is an element at index i,  leftArr[i] is greater than rightArr[j] then it is obvious that all the elements in leftArr[i....mid] will be greater than rightArr[j].

That's all!

Implementation in C#:

    class Solution

    {

        //Complete this function

        //Function to count inversions in the array.

        public long inversionCount(long[] arr)

        {

            long length = arr?.Length ?? 0;

            if (length <= 1)

            {

                return 0;

            }

            return this.CountInversionCount(arr, 0, length - 1);

        }

        

        private long CountInversionCount(long[] arr, long left, long right)

        {

            if (left >= right)

            {

                return 0;

            }

            long mid = left + (right - left) / 2;

            long leftInvCount = this.CountInversionCount(arr, left, mid);

            long rightInvCount = this.CountInversionCount(arr, mid + 1, right);

            long mergeInvCount = this.Merge(arr, left, mid, right);

            return leftInvCount + rightInvCount + mergeInvCount;

        }

        

        private long Merge(long[] arr, long left, long mid, long right)

        {

            List<long> temp = new List<long>();

            long i = left, j = mid + 1;

            long invCount = 0;

            while (i <= mid && j <= right)

            {

                if (arr[i] > arr[j])

                {

                    invCount += (mid - i + 1);

                    temp.Add(arr[j++]);

                }

                else

                {

                    temp.Add(arr[i++]);

                }

            }

            while (i <= mid)

            {

                temp.Add(arr[i++]);

            }

            while (j <=  right)

            {

                temp.Add(arr[j++]);

            }

            i = left;

            for (j = 0; j < temp.Count; ++j)

            {

                arr[i++] = temp[(int)j];

            }

            return invCount;

        }

    }

Complexity: O(nlogn)