Two different answers when using variables that should be the same (mergeSort)

Question

I am a little confused and was looking for some clarification, so I am studying data structures and algorithms and was working on merge sort. Essentially I wanted to return the sorted list and print it to test to see if I had implemented the code correctly, however the lazy scientict I am decided not to copy the data back into the original array and instead just return the temp array. I noticed when I return temp at the end I'll get a different answer than if I returned the original array (named a) after copying back. Was wondering if someone could explain why this occurs. Thank you! Below is the code with the proper print, if you change the return to temp in the merge method you will notice the list stops sorting properly

public class mergeSort {

public static void main(String[] args) {

    int[] a = new int[10];

    for(int i = 0; i < a.length; i++) {

        a[i] = (int)(Math.random()*30+1);
        System.out.println(i + ": " + a[i]);
    }

    mergeSort(a);
}

public static void  mergeSort(int[] a) {


    int[] temp = new int[a.length];

    a = mergeSort(a, 0, a.length, temp);

    for(int i = 0; i < a.length; i++){

        System.out.println(a[i]);
    }

}

public static int[] mergeSort(int[] a, int start, int end, int[] temp) {

    int mid;


    //Recursive method
    if(1 < end-start) {

        mid = start + (end-start)/2;
        mergeSort(a, start, mid, temp);
        mergeSort(a, mid, end, temp);
        a = merge(a, start, mid, end, temp);
    }

    return a;


}

public static int[] merge(int[] a, int start, int mid, int end, int[] temp) {


    int currL = start;
    int currR = mid;
    int currT;

    for(currT = start; currT < end; currT++) {

        if(currL < mid && (currR >= end || a[currL] < a[currR])) {

            temp[currT] = a[currL];
            currL++;
        }

        else{

            temp[currT] = a[currR];
            currR++;
        }

    }

    for(currT = start; currT < end; currT++) {
        a[currT] = temp[currT];
    }

    return a;

} 
}

Eran · Accepted Answer · 2017-10-22T06:08:17.703

Consider:

mergeSort(a, 0, 10, temp);

It calls:

mergeSort(a, 0, 5, temp);
mergeSort(a, 5, 10, temp);
a = merge(a, 0, 5, 10, temp);

After mergeSort(a, 0, 5, temp) returns, the sub-array a[0] to a[5] must be sorted, and after mergeSort(a, 5, 10, temp) returns, the sub-array a[5] to a[10] must be sorted.

This won't happen if merge doesn't modify the original array a is receives.

Note that the assignment a = merge(a, start, mid, end, temp); doesn't change the original array passed to the mergeSort method. Therefore merge itself must modify the array a passed to it, by copying the data from the temp array back to a.

EDIT:

BTW, note that it doesn't matter what merge returns as long as it copied the merged elements from the temp array back to the a array.

You can change its return type to void and the sort will still work:

public static void mergeSort(int[] a, int start, int end, int[] temp) {
    int mid;
    //Recursive method
    if(1 < end-start) {
        mid = start + (end-start)/2;
        mergeSort(a, start, mid, temp);
        mergeSort(a, mid, end, temp);
        merge(a, start, mid, end, temp);
    }  
}

public static void merge(int[] a, int start, int mid, int end, int[] temp) {
    int currL = start;
    int currR = mid;
    int currT;

    for(currT = start; currT < end; currT++) {
        if(currL < mid && (currR >= end || a[currL] < a[currR])) {
            temp[currT] = a[currL];
            currL++;
        } else {
            temp[currT] = a[currR];
            currR++;
        }
    }
    for(currT = start; currT < end; currT++) {
        a[currT] = temp[currT];
    } 
}

Thank you so much for this well written answer! And good point about the return not being needed, should have caught that earlier. Cheers friend! — OVOFan, Oct 22 '17 at 19:11
@OVOFan - You can eliminate the copy step by changing the direction of merge depending on top down level of recursion or bottom up pass. See [this answer](https://stackoverflow.com/questions/46106922/mergesort-algorithm-whats-the-better-implementation-in-java/46107386#46107386) for bottom up and top down examples. — rcgldr, Oct 22 '17 at 21:46

Two different answers when using variables that should be the same (mergeSort)

1 Answers1