Find number of inversions in a given array

Question

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));
 }
 }
}

• maaartinus: 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.

Answer 1

Here are two things that can speed up your code:

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: I did as you say, but the output is not correct any more, generally lower. Do you see what is wrong?
• maaartinus: @mirgee In invCount, you merge from buff into ar, and on the next invocation again.... ar gets never used, strange recursion, isn't it?
• mirgee: @maaartinus It does get used. I save a copy of both merged parts of 'arr' into 'buff' and merge them right into 'arr' again, as user2040251 advised. That works fine, the array is still gets sorted (try to run this, please). But I must be counting the inversions wrong. I fail to see how!
• maaartinus: @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.
• kraskevich: @mirgee Or just completely rewrite it in C++.