Count Inversions In An Array

Problem

Count the number of inversions in a given array of numbers. A pair (nums[i], nums[j]) is said to form an inversion if nums[i] > nums[j] and i < j.

Example 1

{
"nums": [3, 6, 1, 7, 2]
}

Output:

5

Example 2

{
"nums": [5, 10, 15, 18]
}

Output:

0

Solution

function merge(left, right) {

    //Array for storing sorted elements.
    let newArray = [];

    //No. of inversions
    let ni = 0;
    let p = 0;
    let k = 0;

    //For counting inversions
    while (p < left.length && k < right.length) {
        if (left[p] > right[k]) {
            newArray.push(right[k]);
            ni = ni + left.length - p;
            k = k + 1;
        }
        else {
            newArray.push(left[p]);
            p = p + 1;
        }
    }

    //Copies remaining left array elements
    while (p < left.length) {
        newArray.push(left[p]);
        p = p + 1;
    }

    //Copies remaining right array elements
    while (k < right.length) {
        newArray.push(right[k]);
        k = k + 1;
    }
    return [ni, newArray];
}

function countingInversions(a) {
    if (a.length < 2) return [0, a];
    else {
        let mid, left, right, left_inv, right_inv, merged;
        let inversions = 0;

        //Finding middle index.
        mid = Math.floor(a.length / 2);

        //Divides array into left and right.
        left = a.slice(0, mid);
        right = a.slice(mid, a.length);

        //returns inversions and sorted array.
        left_inv = countingInversions(left);
        right_inv = countingInversions(right);

        inversions = inversions + left_inv[0] + right_inv[0];

        //returns inversions and merged array.
        merged = merge(left_inv[1], right_inv[1]);

        //Total number of inversions
        inversions = inversions + merged[0];

        return [inversions, merged[1]];
    }
}

function count_inversions(arr) {
    let result = countingInversions(arr);
    return result[0];
}

Time and Space Complexity

Time Complexity : O(nlogn)
Space Complexity:  O(n)