Number of Inversion Couple

Given an Array, find the number of inversion couples in the Array

e.g. 2, 4, 3, 1

4 -> (2,1), (3,1), (4,1), (4,3)

hint:

Solution 1

* Iterate the whole array twice

* Time: O(N^2)

Solution 2

* Merge Sort

* Time: O(NlogN)

 1 public class InversionCouple {
 2     public int mergeSort(int[] A, int start, int end) {
 3         if (start >= end) return 0;
 4         int mid = start + (end - start) / 2;
 5         int left = mergeSort(A, start, mid);
 6         int right = mergeSort(A, mid+1, end);
 7         int count = 0;
 8         int i = start, j = mid + 1;
 9         int m = mid, n = end;
10         int[] tmp = new int[end-start+1];
11         int run = 0;
12         while (i <= m && j <= end) {
13             if (A[i] <= A[j]) {
14                 tmp[run++] = A[i++];
15             } else {
16                 count += mid - i + 1;
17                 tmp[run++] = A[j++];
18             }
19         }
20         while (i <= m) {
21             tmp[run++] = A[i++];
22         }
23         while (j <= n) {
24             tmp[run++] = A[j++];
25         }
26         /* copy sorted tmp to original array */
27         run = 0;
28         while (run < tmp.length) {
29             A[start + run] = tmp[run];
30             run++;
31         }
32         tmp = null;
33         return count + left + right;
34     }
35     public static void main(String[] args) {
36         int[] A = {1, 7, 2, 9, 6, 4, 5, 3};
37         InversionCouple ic = new InversionCouple();
38         System.out.println(ic.mergeSort(A, 0, A.length-1));
39     }
40 }