countArrayInversions.js

countArrayInversions.js

const countArrayInversions = (arr) => {
    let count = 0;
    let sortedArr = [];
    arr.reverse().forEach(n => {
        // Search in sorted arr for insertion index
        // The number of elements < n in the sorted array are inversions of n
        const i = binaryInsort(sortedArr, n);
        count += i;
    })
    return count;
}

const binarySearch = (arr, n) => {
    let L = 0;
    let R = arr.length - 1;
    while (L <= R) {
        let i = Math.floor((L + R) / 2);
        if (arr[i] < n) {
            L = i + 1;
        }
        else if (arr[i] > n) {
            R = i - 1;
        }
        else {
            return i;
        }
    }
    return L;
}

const binaryInsort = (arr, n) => {
  const i = binarySearch(arr, n);
  arr.splice(i, 0, n);
  return i;
}

//console.log(binarySearch([2], 4));
console.log(countArrayInversions([2, 4, 1, 3, 5])); // 3
console.log(countArrayInversions([5, 4, 3, 2, 1])); // 10

Given an array, count the number of inversions it has. Do this faster than O(N^2) time. You may assume each element in the array is distinct.
We can determine how "out of order" an array A is by counting the number of inversions it has.
Two elements A[i] and A[j] form an inversion if A[i] > A[j] but i < j. That is, a smaller element appears after a larger element.
For example, a sorted list has zero inversions.
The array [2, 4, 1, 3, 5] has three inversions: (2, 1), (4, 1), and (4, 3).
The array [5, 4, 3, 2, 1] has ten inversions: every distinct pair forms an inversion.