# Counting inversions

Inversion Count for an array indicates – how far (or close) the array is from being sorted. If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum. Formally speaking, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j

Example: The sequence 2, 4, 1, 3, 5 has three inversions (2, 1), (4, 1), (4, 3), so answer is 3.

Looking for code-review, optimizations, best practices.

public final class CountingInversions {

private CountingInversions() {}

/**
* Returns the number of inversions in the input array
*
* @param a the input array
* @return  the number of inversions.
*/
public static int countInversions(int[] a) {
return mergeSort(a, 0, a.length);
}

private static int mergeSort (int[] a, int low, int high) {
if (low == high - 1) return 0;

int mid = (low + high)/2;

return mergeSort (a, low, mid) + mergeSort (a, mid, high) + merge (a, low, mid, high);
}

private static int merge (int[] a, int low, int mid, int high) {
int count = 0;
int[] temp = new int[a.length];

for (int i = low, lb = low, hb = mid; i < high; i++) {

if (hb >= high || lb < mid && a[lb] <= a[hb]) {
temp[i]  = a[lb++];
} else {
count = count + (mid - lb);
temp[i]  = a[hb++];
}
}

System.arraycopy(temp, low, a, low, high - low);

return count;
}
}


And the unit tests:

public class CountingInversionsTest {

@Test
public void testOne() {
int[] a1 = {2, 4, 1, 3, 5};
assertEquals(3, CountingInversions.countInversions(a1));
}

@Test
public void testTwo() {
int[] a2 = {4, 3, 2, 1};
assertEquals(6, CountingInversions.countInversions(a2));
}

@Test
public void testThree() {
int[] a3 = {1, 2, 3, 4};
assertEquals(0, CountingInversions.countInversions(a3));
}

@Test
public void testFour() {
int[] a3 = {3, 3, 3, 3};
assertEquals(0, CountingInversions.countInversions(a3));
}
}

• I'd add some bigger tests done by e.g. comparing to bubble sort. With a few such small tests I wouldn't trust the algorithm (and bubble sort is quickly done and testing with 100 random elements can reveal some problems). Jun 20, 2014 at 2:15
• Seems pretty good to me... I tested with some new test cases and it works fine.... Jun 20, 2014 at 17:05

• Both (low + high)>>1 and (low+high)/2 are prone to overflow, the correct expression is (low + high)>>>1 (using unsigned shift). Apr 12, 2015 at 19:23