Merge algorithm

Question

Here is an implementation of merge for mergesort, in Java that works:

void merge(int[] numbers, int low, int mid, int high) {
    int helper[] = new int[numbers.length];
    for (int i = low; i <= high; i++) {
         helper[i] = numbers[i];
    }

    int lowone = low;
    int lowtwo = mid + 1;
    int count = low;

    while (lowone <= mid || lowtwo <= high) {
        if (lowone <= mid && lowtwo <= high) {
            if (helper[lowone] <= helper[lowtwo]) {
                numbers[count] = helper[lowone];
                lowone++;
            } else {
                numbers[count] = helper[lowtwo];
                lowtwo++;
            }
        }
        else if (lowone <= mid) {
              numbers[count] = helper[lowone];
              lowone++;
            }
        else {
              numbers[count] = helper[lowtwo];
              lowtwo++;

        }
       count++;
    }
}
//msort algorithm in case it's relevant
void msort(int[] arr, int low, int high) {
    if (low < high) {
        int mid = (low + high)/2;

        msort(arr, low, mid);
        msort(arr, mid + 1, high);

        merge(arr, low, mid, high);
    }
}

In my first attempt at merge I was trying to have the second half of the array contain the midpoint index instead of having it in the first half. Here is the relavent code (note there are only 4 changes from above):

    int lowtwo = mid;

    while (lowone < mid || lowtwo <= high) {
        if (lowone < mid && lowtwo <= high) {
            if (helper[lowone] <= helper[lowtwo]) {
                numbers[count] = helper[lowone];
                lowone++;
            } else {
                numbers[count] = helper[lowtwo];
                lowtwo++;
            }
        }
        else if (lowone < mid) {
              numbers[count] = helper[lowone];
              lowone++;
        }
        else {
              numbers[count] = helper[lowtwo];
              lowtwo++;   
        }

The modified version used with msort (above) does not correctly sort the list. Maybe it's obvious, but I can't seem to figure out why it doesn't work.

MJD · Accepted Answer · 2012-12-30 05:16:05Z

The problem comes because you change the meaning of mid in merge. The simplest way to look at it is an example. Let's say we have an array with indices:

[0 1 2 3 4]

Calling msort, you'll pass in 0 for low, and 4 for high. That means mid is computed as 2. So you now have the array divided as so (not in memory, just logically):

[0 1 2] [3 4]

Now, when merge is called it's passed in 2 for mid, which is the last index in array 1. However, in you're modified code you treat mid as the starting index for array 2. This makes the two arrays look like:

[0 1] [2 3 4]

Which is different then how everything treats it. An example where this falls down is if you're two array's (after sorting) look like (the numbers are now the values, not indices):

[8 12 14] [7 11]

However, under you're interpretation of mid, the arrays are:

[8 12] [14 7 11]

Which are no longer sorted. Thus you're merge function won't work.

davnicwil · Accepted Answer · 2012-12-30 05:34:36Z

1

It's because you've sorted the two sublists with the midpoint in the first subarray (in msort(...)) before doing the merge with the midpoint in the second subarray (in merge(...)).

Take the simplest example

[2,1]

is split like so (because mid == ((0+1)/2) == 0 )

[2] and [1]

which msort trivially sorts into

[2] and [1]

but then, by placing mid in the second list in the merge, you are in fact merging:

[] and [2,1]

which obviously results in [2,1], which is wrong!

The midpoint placement has to be consistent in both splitting and the merging of the two subarrays.

answered Dec 30, 2012 at 5:34

davnicwil

31.4k21 gold badges116 silver badges135 bronze badges

Collectives™ on Stack Overflow

Merge algorithm

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related