Divide and Conquer Algorithm (MergeSort Algo) calculating number of inversions

Question

I am trying to solve the problem of calculating the number of inversions where the problem is:

`An inversion of a sequence 𝑎0, 𝑎1, . . . , 𝑎𝑛−1 is a pair of indices 0 ≤ 𝑖 < 𝑗 < 𝑛 such that 𝑎𝑖 > 𝑎𝑗. The number of inversions of a sequence in some sense measures how close the sequence is to being sorted. For example, a sorted (in non-descending order) the sequence contains no inversions at all, while in a sequence sorted in descending order any two elements constitute an inversion (for a total of 𝑛(𝑛 − 1)/2 inversions).

Sample Input is: 6 9 8 7 3 2 1

The output will be: 15 `

Now for this, I am trying to merge the sort algorithm and the idea is whenever I will see nextNo. greater than prevNo. I will add count which is 0 initially.

This is the Merge algorithm:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class MergeSort {

static void Merge(int arr[],int l,int m, int r){

    int n1 = m-l+1;
    int n2 = r-m;

    int L[] = new int[n1];
    int R[] = new int[n2];

    for(int i=0;i<n1;i++)
        L[i] = arr[i+l];
    for(int i=0;i<n2;i++)
        R[i] = arr[m+1+i];

    int i=0,j=0;

    int k=l;

    while(i<n1&&j<n2){
        if(L[i]<R[j]){
            arr[k]=L[i];
            i++;
        }
        else{
            arr[k]=R[j];
            j++;
        }
        k++;
    }

    while(i<n1){
        arr[k] =L[i];
        i++;
        k++;
    }

    while(j<n2){
        arr[k] =R[j];
        j++;
        k++;
    }

   }

static void MergeSortBasic(int arr[],int l,int r) {

    if(l<r){
        int m = (l+r)/2;

        MergeSortBasic(arr,l,m);
        MergeSortBasic(arr,m+1,r);

        Merge(arr,l,m,r);
    }
   }

public static void main(String[] args) {
    QuickSortAlgo.FastScanner scanner = new QuickSortAlgo.FastScanner(System.in);
    int n = scanner.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = scanner.nextInt();
    }
  MergeSortBasic(a,0,n-1);
    for (int i = 0; i < n; i++) {
        System.out.print(a[i] + " ");
    }
}

static class FastScanner {
    BufferedReader br;
    StringTokenizer st;

    FastScanner(InputStream stream) {
        try {
            br = new BufferedReader(new InputStreamReader(stream));
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    String next() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }
}
   }

This I understand but here is the solution to this problem that I came across which I could not understand. Can please someone help me in understanding the solution of this algorithm especially the midpoint/ave part.

Solution:

import java.util.*;

public class Inversions {
private static long merge(int[] a, int[] b, int left, int ave, int right) {
    int i = left, j = ave, k = left;
    long inv_count = 0;
    while (i <= ave - 1 && j <= right) {
        if (a[i] <= a[j]) {
            b[k] = a[i];
            i++;
        } else {
            b[k] = a[j];
            inv_count += ave - i;
            j++;
        }
        k++;
    }
    while (i <= ave - 1) {
        b[k] = a[i];
        i++;
        k++;
    }
    while (j <= right) {
        b[k] = a[j];
        j++;
        k++;
    }
    for (i = left; i <= right; i++) {
        a[i] = b[i];
    }
    return inv_count;
}

private static long getNumberOfInversions(int[] a, int[] b, int left, int right) {
    long inv_count = 0;
    if (right <= left) {
        return inv_count;
    }
    int ave = left + (right - left) / 2;
    inv_count += getNumberOfInversions(a, b, left, ave);
    inv_count += getNumberOfInversions(a, b, ave + 1, right);
    inv_count += merge(a, b, left, ave + 1, right);
    return inv_count;
}

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = scanner.nextInt();
    }
    int[] b = new int[n];
    System.out.println(getNumberOfInversions(a, b, 0, a.length - 1));
}
}

My question is Why do we have

inv_count += ave - i;

Instead of simply:

inv_count++;

Like what is the difference between these two programs?? How is this ave variable working? Also, any idea how can I learn this effectively in the future?

Answer 1

why: inv_count += ave - i;

The two sub-arrays being merged are already sorted from prior recursions (or an end case where sub-array size is 1 element). Each time an element from the right sub-array is found to be less than the current element in the left sub-array (a[j] < a[i]), the number of elements remaining in the left sub-array (ave - i) is added to the inversion count, because a[j] is less than all of the elements from a[i] through a[ave-1].