Issue with understanding fencepost handling with merge-sort

Question

Fencepost (AKA An off-by-one error (OBOE), also commonly known as an OBOB (off-by-one bug).

Given an array, I would generally iterate through index 0 to array.length() (Half-open interval).

I've noticed that certain versions of merge-sort require the mid value to be (start+end)/2. And when you calculate the number of elements in the merge process then we sometimes refer to using (end - start) as number of elements or (end - mid + 1). I am not able to intuitively get this? I somehow have difficulty understanding this and feel like am mugging up each time I look at any new implementation.

Can someone provide an intuitive way to understanding how I can apply/recognize a fencepost problem? Is this the same for multi-dimensional arrays?

public static BigInteger mergeSort(int[] integerArray, int start, int end) {
    if (start >= end) { // less than equal to is important for cases when start = end = 0
        return BigInteger.valueOf(0);
    }
    int middle = (start + end) / 2;
    BigInteger numInv1 = mergeSort(integerArray, start, middle);
    BigInteger numInv2 = mergeSort(integerArray, middle + 1, end);
    BigInteger numInv3 = runMerge(integerArray, start, middle, end);
    return numInv1.add(numInv2).add(numInv3);
}

private static BigInteger runMerge(int[] integerArray,
                                   int start, int middle, int end) {
    BigInteger numInv = BigInteger.valueOf(0);
    int n1 = middle - start + 1;
    /*
    number of elements in 1st array is middle - start + 1. why ?
    */

    int n2 = end - middle;       // number of elements in 2nd array
    /*
    number of elements in 2nd array is end - middle. why ?
    */

    int []p = new int[n1];
    int []q = new int[n2];
    int i, j, k;
    for (i = 0; i < n1 ; i++) {
        p[i] = integerArray[start + i];
    }
    for (j = 0; j < n2; j++) {
        q[j] = integerArray[middle + j + 1];
        //Why do we do +1 here? because we use 2nd array for mid+1 till end elements
    }
    i = 0;
    j = 0;
    k = start;
    while ( i < n1 && j < n2) {
        if (p[i] <= q[j]) {
            integerArray[k++] = p[i++];
        } else {
            integerArray[k++] = q[j++];
            numInv = numInv.add(BigInteger.valueOf(n1-i));
        }
    }
    while ( i < n1 ) {
        integerArray[k++] = p[i++];
    }
    while ( j < n2 ) {
        integerArray[k++] = q[j++];
    }
    return numInv;
}

curveball · Answer 1 · 2017-07-22T12:16:55.130

number of elements in 1st array is middle - start + 1. why? number of elements in 2nd array is end - middle. why?

They are not numbers of elements, they are elements' edge indexes needed to break initial array into smaller arrays. Suppose you have an array to sort:

int[] myIntArray = {7,4,3,5,1,12,12,11,0,2};

It contains 10 elements but the indexes go from 0 to 9. So, in your method mergeSort(int[] integerArray, int start, int end); it should be myIntArray, 0, 9, not myIntArray, 1, 10 nor myIntArray, 1, 9.

So, assuming we pass arguments like myIntArray, 0, 9, lets look into the last (folding direction) call of mergeSort() when we have two sorted subarrays:

After calculating middle = (0 + 9) / 2 = 4, we mentally broke our initial array into 2 arrays like this:

mergeSort(integerArray, start, middle); where start = 0 and middle = 4 (comprises the items with indexes from 0 to 4 - both included: 1,3,4,5,7)

and

mergeSort(integerArray, middle + 1, end); where start = middle + 1 = 4 + 1 = 5 and end = 9 (comprises the numbers with indexes from 5 to 9 - both included: 0,2,11,12,12).

Here

q[j] = integerArray[middle + j + 1];

by adding +1 we are getting to the 5th element. Remember that in the stack for the current call variable middle is equal to 4 and this value (4) was passed to runMerge(). Value middle + 1 went to one of the previously finished calls of mergeSort().

The whole proceeding goes on untill we get arrays of size 1 that can be considered sorted and then we start to merge - sure, you already know this. As you can see, those variables - start, middle, end - are the positions (indexes) of elements and not numbers of elements.

The code you posted works fine if you treat arguments as items' positions like mergeSort(myIntArray, 0, 9); and not as number of items. In the beginning it should be array.length() - 1 Hope it helps :)

Issue with understanding fencepost handling with merge-sort

1 Answers1