Trouble with Merge Sort Bug

Question

I'm trying to implement merge sort and am getting stuck with the merge function:

Here is my function:

public static void merge(Comparable[] a, Comparable[] aux, int low, int mid, int hi) {
    // Copy the elements to the aux array
    for(int i = low; i < a.length; i++) {
        aux[i] = a[i];
    }

    int i = low, j = mid + 1;
    for (int k = low; k <= hi; k++) {
        if      (i > mid)              a[k] = aux[j++];
        else if (j > hi)               a[k] = aux[i++];
        else if (less(aux[j], aux[i])) a[k] = aux[j++];
        else                           a[k] = aux[i++];
    }
}

Running the following input:

[2, 4, 6, 8, 3, 5, 7, 9]

Produces this result:

[2, 3, 3, 3, 3, 5, 7, 9]

Here is the call itself:

    int mid = 0 + (my_array.length - 0) / 2;
    MergeSort.merge(my_array, my_array, 0, mid -1, my_array.length-1);

I can't quite nail it down.

Answer 1

a and aux are the same array. So, you first copy the array into itself, which is quite useless. Then, in the second loop, you change the value as it is being read, which mess everything up.

Instead of passing two (identical) arrays, create a new one in the merge method and return it.