I tried this. initd the merge arrays outside the recursive calls and passed them in but it still times out on some test cases. Could you figure out why?

import java.io.; import java.math.; import java.security.; import java.text.; import java.util.; import java.util.Map.Entry; import java.util.concurrent.; import java.util.regex.*;

public class Solution {

// Complete the countInversions function below.

static long countInversions(int[] arr) {

   long inversionsCount = 0;

   int [] lowerArray = new int [arr.length]; 
   int [] higherArray = new int [arr.length]; //frm mid+1 to high


   inversionsCount = countAndSort (arr, 0, arr.length - 1, lowerArray, higherArray);
   return inversionsCount;
}

static long countAndSort(int [] arr, int low, int high, int [] lowerArray, int [] higherArray)
{
    long totalCount = 0;
    long count = 0;
    if (low < high)
    {
        int mid = low + (high-low) /2;

        long lowerCount = countAndSort (arr, low, mid, lowerArray, higherArray);
        long higherCount = countAndSort (arr, mid+1, high, lowerArray, higherArray);
        totalCount += lowerCount + higherCount + countAndSortMerge (arr, low, mid, high, lowerArray, higherArray);
    } 

    return totalCount;
}

static long countAndSortMerge(int [] arr, int low, int mid, int high, int [] lowerArray, int [] higherArray)
{
    long countInversions = 0;

    for (int i=0; i< (mid-low+1);i++)
    {
        lowerArray[i] = arr [low+i];
    }

    for (int i=0; i< (high-mid);i++)
    {
        higherArray[i] = arr [mid+1+i];
    }

    int lowIndex = 0;
    int highIndex = 0;
    int arrIndex = low;

    while (lowIndex < (mid-low+1) && highIndex < (high-mid))
    {
        if (lowerArray[lowIndex] <= higherArray [highIndex])
        {
            arr[arrIndex] = lowerArray[lowIndex];

            ++lowIndex;
        }
        else
        {
            arr[arrIndex] = higherArray[highIndex];

            ++highIndex;
            countInversions += (mid-low+1 - lowIndex);
        }

        ++arrIndex;
    }


    while (lowIndex < (mid-low+1))
    {
        arr[arrIndex] = lowerArray[lowIndex];

        ++lowIndex;
        ++arrIndex;
    }

    while (highIndex < (high-mid))
    {
        arr[arrIndex] = higherArray[highIndex];

        ++highIndex;
        ++arrIndex;
    }

    System.out.printf("CountandsortMerge inversions - %d", countInversions);
    return countInversions;

}

private static final Scanner scanner = new Scanner(System.in);

public static void main(String[] args) throws IOException {
    BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    int t = scanner.nextInt();
    scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

    for (int tItr = 0; tItr < t; tItr++) {
        int n = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        int[] arr = new int[n];

        String[] arrItems = scanner.nextLine().split(" ");
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int i = 0; i < n; i++) {
            int arrItem = Integer.parseInt(arrItems[i]);
            arr[i] = arrItem;
        }

        long result = countInversions(arr);

        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();
    }

    bufferedWriter.close();

    scanner.close();
}

}

Actually len() also matters, especially inside the loop. I had

inversions += len(arr0[i0:])

instead of

inversions += len0 - i0

and it was timing out because when slicing, Python creates a copy, making it O(n) opperation.

Thank you for the code.

I also used indices. Additionally, I used nested functions to avoid generating new arrays by keeping the original and the auxiliary one in scope (along with a "Context" class to make the counter variable accessible).

Instead of using built-in functions or slicing to build the new array, I just iterated through it and assigned each element a new value. I made this possible by initializing the new array as a pointer to the original and initializing the auxiliary one as a copy of the original; this way, we have a pre-determined size that allows for iteration.

P.S. This was written in Python 2 (without using PyPy). This times out on the last three cases.

#!/bin/python
import sys


def merge_sort(arr):

    class Context:
        count = 0

    def merge(*indices):           # indices = first, last, and pivot indices, respectively
        head, tail = indices[0], indices[1]
        pivot = indices[2]

        i = head
        j = pivot+1
        k = 0

        while (i <= pivot and j <= tail):
            if new[i] <= new[j]:
                aux[k] = new[i]
                i += 1
                k += 1
            else:
                aux[k] = new[j]
                j += 1
                k += 1
                Context.count += pivot - i+1
        while (i <= pivot):
            aux[k] = new[i]
            i += 1
            k += 1
        while (j <= tail):
            aux[k] = new[j]
            j += 1
            k += 1

        for x in xrange(head, tail+1):
            new[x] = aux[x-head]
        # end merge

    def split(a, *indices):      # indices = first and last indices, respectively
        head, tail = indices[0], indices[1]
        pivot = (head+tail) / 2

        if head < tail:
            l_sub = a[head:pivot+1]
            r_sub = a[pivot+1:tail+1]

            split(l_sub, head, pivot)
            split(r_sub, pivot+1, tail)
            merge(head, tail, pivot)
        # end split

    new = arr
    aux = list(new)
    tail = len(new)-1

    split(new, 0, tail)
    return Context.count
    # end merge_sort


if __name__ == "__main__":
    loops = int(raw_input().strip())
    for _ in xrange(loops):
        useless_var = int(raw_input().strip())
        arr = map(int, raw_input().strip().split(' '))
        result = merge_sort(arr)
        print result

Guys please help,

Why is:

inversions = len0-i0

Why not:

inversions = inversion +1

This is quite true and is terribly misleading.

Furthermore, the description is misleading because the example from the problem description of |2, 1, 3, 1, 2| is an example of isertion sort, not merge sort.

input = [2, 1, 3, 1, 2]
swap_1 = [1, 2, 3, 1, 2]
swap_2 = [1, 2, 1, 3, 2]
swap_3 =[1, 1, 2, 3, 2]
swap_4 = [1, 1, 2, 2, 3]

4 steps -> insertion sort

Merge Sort does not swap, but rather divides the array by 2, recursively (O log(n)), and then creates a new array, each divided part is added one at a time with its complement half, in the correct order (O (n)) Total calculation O(n*log(n)), in this way:

After arrays are divided, they are joined like this:

input = [2, 1, 3, 1, 2]
merge_1 = [1, 2, 3, 1, 2]
merge_2 = [1, 2, 1, 2, 3]
merge_3 = [1, 1, 2, 2, 3]

3 steps -> merge sort

Since, this is a merge sort algo, yet, expects the counts to be unrelated to merge sort, I find this to be particularly confusing question.

what you described is not a merge sort algorithm. seems the author of the task wants two conflicted things: 1. calculate Insert Sort swaps 2. but to provide O(n*log(n)) complexity (use e.g. MergeSort )

is not it?

The only tricky part here is how to merge two sorted arrays. Here is my similar solution. Might be slightly easier to understand because of less number of arguments. Though, I recommend to think as much as you can before looking into the solution. :

public static long countInversions(int[] arr){
        
        return mergeSort(arr, 0, arr.length - 1);
    }
    
    public static long mergeSort(int[] arr, int start, int end){
        if(start == end)
            return 0;
        int mid = (start + end) / 2;
        long count = 0;
        count += mergeSort(arr, start, mid); //left inversions
        count += mergeSort(arr, mid + 1, end);//right inversions
        count += merge(arr, start, end); // split inversions.
        return count;
    }
    
    public static long merge(int[] arr, int start, int end){
        int mid = (start + end) / 2;
        int[] newArr = new int[end - start + 1];
        int curr = 0;
        int i = start;
        int j = mid + 1;
        long count = 0;
        while(i <= mid && j <=end) {
            if(arr[i] > arr[j]) {
                newArr[curr++] = arr[j++];
                count += mid - i + 1; // Tricky part.
            }
            else
                newArr[curr++] = arr[i++];          
        }
         // Leftover elements here.
        while(i <= mid) {
            newArr[curr++] = arr[i++];    
        }
        
        while(j <= end) {
            newArr[curr++] = arr[j++];
        }
     
        System.arraycopy(newArr, 0, arr, start, end - start + 1); // Usual stuff from merge sort algorithm with arrays.
        return count;
    }

I did this course some time ago, but now I cannot find it anymore :( Does anyone know where I can get the course material from?

thanks a lot it really helped. this guys lecture was really good.

Can anyone help with this? I'm getting output 5 where I should get 4 in the 2nd sample.

long long merge(vector<int> arr, int l, int h){
    int aux[h-l+1];
    int mid = (l+h)/2;
    int i=l, j=mid+1, k=0, count=0;
    
 
    while(i<=mid&&j<=h){
        if(arr[j]<arr[i]){
            aux[k] = arr[j];
            j++;
            count+=mid-i+1;
            
        }
        else{
            aux[k] = arr[i];
            i++;
        }
        k++;
    }
    while(i<=mid){
        aux[k] = arr[i];
        i++;
        k++;
    }
    while(j<=h){
        aux[k] = arr[j];
        j++;
        k++;
    }
    
    k=0;
    for(int x=l;x<=h;x++){
        arr[x] = aux[k];
        k++;
    }
    
    return count;
}

long long mergeSort(vector<int> arr, int lo, int hi){
    if(lo>=hi) return 0;
    
    int mid = (lo+hi)/2, count=0;
    
    count+=mergeSort(arr, lo, mid);
    count+=mergeSort(arr, mid+1, hi);
    count+=merge(arr, lo, hi);
    
    return count;
}

long long count_inversions(vector<int> a) {
    
    return mergeSort(a, 0, a.size()-1);
}

Thanks for your help. saved my day

Whenever we pick a number from the right array because it is smaller than the left array, then we have to add to the inversions. How many? The length of the remainder of the left array."

Thanks, that gave the answer away! So basically a straightforward merge sort with that extra line.

Here's my answer in javascript

// Complete the countInversions function below.
function countInversions(arr) {

let count=0;
mergesort(arr)

function mergesort(myar){
if (myar.length==1) return myar;
let mid= Math.floor(myar.length/2);
const a1= mergesort(myar.slice(0,mid));
const a2= mergesort(myar.slice(mid));
return merge(a1,a2);
}

function merge(a1,a2){
let ptrA=0;
let ptrB=0;
const NewArr=[];
while ((ptrA <a1.length) && (ptrB < a2.length)){
if (a1[ptrA] <= a2[ptrB]){
NewArr.push(a1[ptrA]);
ptrA++
} else {
NewArr.push(a2[ptrB]);
ptrB++
// and here's the extra line to get the count
count=count + (a1.length-ptrA)
}}
for (let i=ptrA; i<a1.length;i++){NewArr.push(a1[i])}
for (let i=ptrB; i<a2.length;i++){NewArr.push(a2[i])}
return NewArr

}

return count;

}