CODEWITHSUNDEEP
javarecursionmergesort
aymaluser
aymaluser

Reputation: 13

Java merge sort recursion strangeness

I was doing some review on sorting algorithms since they don't actually come up that often in real life for me, and this one about drove me mad. I've also not done Java in a while so I thought maybe I had forgotten some language esotarica, but I don't think so.

What I found is that success or failure depends on how I make the recursive call to split the array. So, if I use the return value of the split call as a parameter to the merge call, it works. However, if I call split recursively first, then call merge, it fails. However, it seems to me that they should both work. It seems to have something to do with how the stack unwinds, but I can't quite wrap my head around it. 

static Comparable[] mergesort(Comparable[] src) {
    if (src.length < 2)
        return src;

    int middle = src.length / 2;
    if (src.length % 2 > 0)
        middle++;

    Comparable[] left = new Comparable[src.length / 2];
    Comparable[] right = new Comparable[middle];

    System.arraycopy(src, 0, left, 0, left.length);
    System.arraycopy(src, src.length / 2, right, 0, right.length);

    // THIS DOESN'T WORK, BUT I DON'T KNOW WHY
    // mergesort(left);
    // mergesort(right);
    // return mergearrays(left, right);
    // ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    // 
    // THIS ONE DOES WORK
    // 
    return mergearrays(mergesort(left), mergesort(right));
}

static Comparable[] mergearrays(Comparable[] left, Comparable[] right) {

    Comparable[] retval = new Comparable[left.length + right.length];

    int i = 0, j = 0, k = 0;
    for (; i < left.length && j < right.length;) {
        if (left[i].compareTo(right[j]) >= 0) {
            retval[k++] = right[j++];
        } else
            retval[k++] = left[i++];

    }

    while (k < retval.length) {
        if (i < left.length) {
            retval[k++] = left[i++];
        }
        if (j < right.length) {
            retval[k++] = right[j++];
        }
    }

    return retval;
}

Upvotes: 1

Views: 93

Answers (1)

Eran
Eran

Reputation: 393831

Your mergearrays method creates a new array in which it stores the merged sorted array. Therefore if you don't use the arrays returned by mergesort(left) and mergesort(right) (which are themselves arrays created by previous calls to mergearrays), you are discarding the sorted arrays and passing unsorted arrays (left and right) to mergearrays.

Therefore this code is wrong:

mergesort(left); // returns a new sorted array which you ignore, doesn't modify left
mergesort(right); // returns a new sorted array which you ignore, doesn't modify right
return mergearrays(left, right); // merges two unsorted arrays, and therefore is wrong

While this code is right:

// merges the two sorted arrays returned by mergesort(left) and mergesort(right)
return mergearrays(mergesort(left), mergesort(right));

Some merge sort implementations perform the merge step on the original array (i.e. they sort the array in place instead of returning a new sorted array), in which case neither the mergearrays method nor the mergesort need to return anything, and the following can work:

mergesort(left);
mergesort(right);
mergearrays(left, right);

Upvotes: 1

Related Questions