Thread: Why does this MergeSort implementation not receive IndexOutOfBondsExpception

Hi there I have this implamentation of the MergeSort algorithm from a text book and it looks like this:

public static void mergeSort(int[] array) {
if(array.length > 1) {
int[] left = leftHalf(array);
int[] right = rightHalf(array);
 
mergeSort(left);
mergeSort(right);
 
merge(array, left, right);
}
}

The leftHalf and rightHalf respectively return the left and right halves of the original array, no tricks there!

And then I have the merge method:

public static void merge(int[] result, int[] left, int[] right) {
 
int i1 = 0;
int i2 = 0;
 
for(int i = 0; i < result.length; i++) {
if(i2 >= right.length || (i1 < left.length && left[i1] <= right[i2])) {
 
result[i] = left[i1];
i1++;
} else {
 
result[i] = right[i2];
i2++;
}
}
}
}

So as far as I can understand if you call this mergeSort with an array of:

int[] list = {42, 17, 33, 55};

Then we get mergeSort doing the following calls:

mergeSort(list);
left = 42, 17
right = 33, 55
mergeSort(left);
left = 42;
right = 17;
mergeSort(left); // Nothing happens bottoms out
mergeSort(right); // Nothing happens bottoms out
merge(array, left (42), right (17));

So as far as I can see we are calling merge with an array of length four (array), and two arrays of length 1.
So why do we not get a call that is out of bounds in the two arrays of length of 1, in our merge method?
As far as I can see, after two traversals of the for loop, we would end up with both i1 = i2 = 1.

And then we would get a call right[1] which is not legal.

So what is wrong?

Might there be a helpful soul out there?

Bump!

If I understand correctly you are asking why there is no out of bounds when it breaks it down to a single element array. The answer to your question is that this is a recursive method. It calls itself from within andruns the code inside each time. As you can see at the beginning of the method it checks to make sure the array size contains more than 1 element otherwise it does not run the code.

What the code is doing

1. Passing an array to mergeSort method
2. Checks the size of the array if the array contains more than 1 element it runs code
3. Breaks the array into 2 different array a left and a right side
4. Calls mergeSort with left side of array (mergeSort(leftSide))
5. Repeats steps 2 - 4 until array's are broken down to 1 element then returns to previous stack to continue running code.
6. Does same thing as before but now with the right side of the array (mergeSort(rightSide))

Each recursive call adds to the stack and once the code is completely executed in a stack it returns to the previous stack to execute the rest of the code. As you can see you never get the index out of bounds from right[1] because that case does not happen in the code. As soon as the array contains only 1 element it skips the code that breaks the array in half.

With this type of problem it makes it makes things a lot easier when you draw them out on paper and understand what the code is doing.