Counting inversions

Question

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

• maaartinus: 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).
• Debasis: Seems pretty good to me... I tested with some new test cases and it works fine....

Answer 1

The code is well written. Some specific remarks are as follows.

• A better name of the class would be InversionCounter.
• You don't really need to create the temporary array temp every time merge is called. Since, merge is called recursively for every level you might start noticing performance issues with very large input sizes. A better approach would be to allocate temp as a class member. The size of temp should be equal to the size of the original array. For each subsequent calls to temp you would be using smaller and smaller parts of temp. But you don't need to call the memory manager anymore for every call to merge.
• It's a better idea to pass the array as a constructor argument to the class InversionCounter. You can then allocate temp in the constructor itself.
• Make the method non-static and create a new instance of InversionCounter each time.
• A better name of temp would be buff.
• Some might suggest that (low + high)>>1 is supposed to be faster than (low+high)/2 but with modern compiles with full optimization, I don't think it's a problem.
• You don't need to pass around the array a[] in the helper functions if you make the functions non-static and make a[] a class member.

• maaartinus: Both (low + high)>>1 and (low+high)/2 are prone to overflow, the correct expression is (low + high)>>>1 (using unsigned shift).