# Find number of inversions in a given array

Can you please give me a hint on how to improve performance of the following algorithm meant to find the number of inversions in a given array?

/* *
* INPUT:
* 1. t : number of test cases; t test cases follow
* 2. n : number of elements to consider in each test case
* 3. ar[i] : n numbers, elements of considered array
* */

import java.util.*;

public class Inversions1 {

public static long[] ar;
public static long[] buff;

// Merges arrays left[] and right[] into ar[], returns number of
// inversions found in the process
public static long merge(int low, int middle, int high) {
int i = low;
int j = middle + 1;
int k = low;
long count = 0;

for(int l = low; l <= high; l++) {
buff[l] = ar[l];
}

while (i <= middle && j <= high) {
if (buff[i] <= buff[j]) {
ar[k] = buff[i];
i++;
} else {
ar[k] = buff[j];
j++;
count += middle-i+1;
}
k++;
}

while (i <= middle) {
ar[k] = buff[i];
i++; k++;
}
while(j <= high) {
ar[k] = buff[j];
j++; k++;
}
return count;
}

// Traditional merge sort on arr[], returns number of inversions
public static long invCount(int low, int high) {
if(low < high) {

int middle = low + (high - low)/2;

return invCount(low, middle) + invCount(middle+1,high) + merge(low, middle, high);
}
return 0;
}

public static void main (String args[]) {
int t, n;
Scanner sc = new Scanner(System.in);
t = sc.nextInt();
while(t-- > 0) {
n = sc.nextInt();
ar = new long[n];
buff = new long[n];
for(int i = 0; i < n; i++) {
ar[i] = sc.nextLong();
}
System.out.println(invCount(0,n-1));
}
}
}

• Irrelevant to performance, but I'd suggest to get rid of this static everywhere. Create a class encapsulation the data and let it do its job. Aug 18, 2014 at 6:32

1. Using custom scanner instead of java.util.Scanner. You can create it using BufferedReader and StringTokenizer. It speeds up input significantly.
2. Avoiding allocation of left and right arrays inside invCount functions. To do it, you can rewrite your merge and invCount function so that they always use your initial array and take lower and upper bound indices. Merging would require additional buffer anyway, but it can be allocated only once (before any merge is executed). So there would be only two array allocations per test case. It would probably make you code slightly longer and less readable, but it should make it faster.
• @mirgee In invCount, you merge from buff into ar, and on the next invocation again.... ar gets never used, strange recursion, isn't it? Aug 18, 2014 at 6:31
• @mirgee For the input 5 1 6 2 7 0 I get 0 6 1 0 7. No idea, what it means, just write a proper automated test showing that the sorting works. It's surely easier than writing some input manually twice or more. Aug 18, 2014 at 11:05