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

Sorry, prakashaditya, I missed your question...

Here comes the explanation: https://wiki.python.org/moin/PythonSpeed#Take_advantage_of_interpreter_optimizations

Because we have already compared with mid. If you are checking the left and right sub arrays, this means that mid is definitely not our answer. So we can skip it

left_half ends at mid - 1. No elements are common between the left and the right halves.

I was having problems in Python 3 where I would keep calling len() to get the length of my current array for each loop I was doing. When I initialized two variables with "l = len(left)" and "r = len(right)" at the beginning of my merging function, the time seemed to reduce enough to pass all test cases. Here is what I mean by that:

def merge(left, right, inversions): new = [] i = j = 0 if left == None: left = [] if right == None: right = [] l = len(left)#!!!!!!!!! r = len(right)#!!!!!!!!

while i < l and j < r:  #before while i < len(left) and j < len(right) 
    if left[i] <= right[j]: 
        new.append(left[i])
        i += 1
    else: 
        inversions[0] += (l - i)
        new.append(right[j])
        j += 1
while i < l:  #before: while i < len(left) 
    new.append(left[i])
    i += 1
while j < r:  #before: while j < len(right) 
    new.append(right[j])
    j += 1
return new

Previously, when I was using "while i < len(left) and j < len(right)", "while i < len(left)" and "while j < len(right) " the program would not pass all test casses (although, I wouldn't think the len() function actually takes that long).

Hope this clarified my post.

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 you explain how swaping the aux array saves extra time;

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

this got me too. Very frustrating. Here is Scanner code that works.

Thanks @doktoren for the lead.

(Credit to Martin R on StackExchange for this code https://codereview.stackexchange.com/users/35991/martin-r)

public func splitToIntegers(_ s: String, count: Int) -> [Int] {
    var result: [Int] = []
    result.reserveCapacity(count)
    var n = 0
    let scanner = Scanner(string: s)
    while scanner.scanInt(&n) {
        result.append(n)
    }
    return result
}

let d = Int(readLine()!)!
for _ in 0..<d {
  let length = Int(readLine()!)!
  let ary = splitToIntegers(readLine()!, count: length)
  //...
 }