Writing An Effective Merge

Recently I've been implementing simple algorithms from scratch from memory. As an exercise, this has the advantage of being short, well-defined and (for me at least) challenging. For example, I found it surprisingly hard to write an effective merge of the kind needed for the mergesort algorithm.

The spec is void merge(int[] a, int lo, int mid, int hi): two parts of the array are to be merged. It's assumed the two parts are already sorted. The two parts are adjacent; the first part includes the items from lo to mid - 1; the second is the items from mid to hi - 1.

Here's my first attempt, rushed out late at night.

    private void merge(int[] a, int lo, int mid, int hi) {
        assert mid == lo + (hi - lo) / 2;
        List<Integer> result = new ArrayList<Integer>();
        int i = lo;
        int j = mid;

        while (i < mid && j < hi) {
            int m = a[i];
            int n = a[j];
            if (m > n) {
                result.add(n);
                j++;
            } else {
                result.add(m);
                i++;
            }
        }
        while (i < mid) {
            result.add(a[i++]);
        }
        while (j < hi) {
            result.add(a[j++]);
        }
        for (i = lo, j = 0; j < result.size(); i++, j++) {
            a[i] = result.get(j);
        }
    }
}

It did the job, but oh my, how I didn't like it. It's verbose and it creates this temporary list of O(n) size. After some more work and several blind alleys, I came up with the following. It's better, but still, it seems harder than it should be. Oddly enough, I found it easier to implement quicksort from scratch than just the merge portion of mergesort.

    private void merge(int[] a, int lo, int mid, int hi) {
        assert mid == lo + (hi - lo) / 2;
        int i = lo;
        int j = mid;
        while (i < mid) {
            if (a[j] < a[i]) {
                swap(a, i, j);
                j++;
            }
            i++;            
        }
        if (j < hi) {
            while (a[j] < a[i]) {
                swap(a, i, j);
                i++;
            }
        }
    }

    private void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

Finally, the tests I wrote while working this out:

public void testEmpty() {
    int [] a = new int[0];
    merge(a, 0, 0, 0);
    assertEquals(0, a.length);
}

public void testSingleValue() {
    int [] a = new int[] { 1 };
    merge(a, 0, 0, 1);
    assertArraysEqual(new int[] { 1 }, a);
}

public void testTwoValuesRequiringNoSwap() {
    int [] a = new int[] { 1, 2 };
    merge(a, 0, 1, 2);
    assertArraysEqual(new int[] { 1, 2 }, a);
}

public void testTwoValuesRequiringSwap() {
    int [] a = new int[] { 2, 1 };
    merge(a, 0, 1, 2);
    assertArraysEqual(new int[] { 1, 2 }, a);
}

public void testSimpleInterleavedMerge() {
    int [] a = new int[] { 1, 3, 2, 4 };
    merge(a, 0, 2, 4);
    assertArraysEqual(new int[] { 1, 2, 3, 4 }, a);
}

public void testMergeOfSubset() {
    int [] a = new int[] { 1, 3, 2, 4, 6, 5 };
    merge(a, 0, 2, 4);
    assertArraysEqual(new int[] { 1, 2, 3, 4, 6, 5 }, a);
}

public void testMergeOfAllEqual() {
    int [] a = new int[] { 1, 1, 1, 1 };
    merge(a, 0, 2, 4);
    assertArraysEqual(new int[] { 1, 1, 1, 1 }, a);
}

public void testMergeAllFromRight() {
    int [] a = new int[] { 3, 4, 1, 2 };
    merge(a, 0, 2, 4);
    assertArraysEqual(new int[] { 1, 2, 3, 4 }, a);
}

public void testMergeAllFromLeft() {
    int [] a = new int[] { 1, 2, 3, 4 };
    merge(a, 0, 2, 4);
    assertArraysEqual(new int[] { 1, 2, 3, 4 }, a);
}

public void testMergeUnevenNumber() {
    int [] a = new int[] { 3, 1, 2 };
    merge(a, 0, 1, 3);
    assertArraysEqual(new int[] { 1, 2, 3 }, a);
}

public void testMergeLargerList() {
    int [] a = new int[] { 5, 6, 7, 1, 2, 3, 4 };
    merge(a, 0, 3, 7);
    assertArraysEqual(new int[] { 1, 2, 3, 4, 5, 6, 7 }, a);
}