CODEWITHSUNDEEP
javaalgorithmsortingmergesort
Anupam Sinha
Anupam Sinha

Reputation: 123

Merge method in mergesort implementation includes unneccessary right sub array copy?

I have a query regarding the merge method in merge sort algo. I have copied the below code from http://algs4.cs.princeton.edu/22mergesort/Merge.java.html. I am unable to understand why do we need to copy the right sub array.

This statement 

if (i > mid) index[k] = aux[j++];

copies the right sub array over the right sub array. So it basically overwrites the same values. I feel that if i has crossed mid then

  1. The left sub array values are completely sorted.
  2. The right sub array is also sorted till j.
  3. All entries after j (including j) are already sorted and the aux array and the original array(a) have the same entries.

So it looks like we can do away with the copy to right subarray statement if i has crossed mid.

Or maybe I am missing a use case. Do let me know if you are able to figure it out.

// code begins

private static void merge(Comparable[] a, int[] index, int[] aux, int lo, int mid, int hi) {

    // copy to aux[]
    for (int k = lo; k <= hi; k++) {
        aux[k] = index[k]; 
    }

    // merge back to a[]
    int i = lo, j = mid+1;
    for (int k = lo; k <= hi; k++) {
        if      (i > mid)                    index[k] = aux[j++];
        else if (j > hi)                     index[k] = aux[i++];
        else if (less(a[aux[j]], a[aux[i]])) index[k] = aux[j++];
        else                                 index[k] = aux[i++];
    }
}

Upvotes: 3

Views: 679

Answers (1)

templatetypedef
templatetypedef

Reputation: 373042

I believe that you are correct - that copy step does seem unnecessary for precisely the reason you've pointed out.

This might be an artifact of an older version of the merge function in which the two arrays to sort were not stored adjacent to one another in the input array. If the input arrays were stored in two independent arrays, there would have to be a final copy step to move all unused elements from one of the arrays into the result array after the other array was exhausted. Due to the way to the elements are stored in the input array, you are correct that this step might not be necessary.

Hope this helps!

Upvotes: 1

Related Questions