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 '14 at 6:32