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.

Answer 1

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.