Why does this MergeSort implementation not receive IndexOutOfBondsExpception

• August 28th, 2013, 12:21 PM
lo22
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:

Code :

```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:

Code :

```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:

Code :

`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?
• August 30th, 2013, 11:06 AM
lo22
Re: Why does this MergeSort implementation not receive IndexOutOfBondsExpception
Might there be a helpful soul out there?

Bump!
• August 30th, 2013, 11:55 AM
Norm
Re: Why does this MergeSort implementation not receive IndexOutOfBondsExpception
Can you post a complete program that compiles and executes and shows the problem? Make sure the code is properly formatted. Logically nested statements should be indented 3-4 spaces.

Try debugging the code by adding some calls to the println() method that prints out the values of the variables as the code executes.
For arrays: System.out.println("an ID "+ java.util.Arrays.toString(theArrayName));
• September 2nd, 2013, 06:23 PM
Ubiquitous
Re: Why does this MergeSort implementation not receive IndexOutOfBondsExpception
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
Code :

```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.
• September 3rd, 2013, 11:03 AM
aussiemcgr
Re: Why does this MergeSort implementation not receive IndexOutOfBondsExpception
Here is a general trace of what would happen in your case. Each * should be considered one extra level of recursion:

Code java:

```int[] list = {42, 17, 33, 55};   mergeSort(array0 = list) left0 = {42,17} right0 = {33,55} *mergeSort(array1 = left0) *left1 = {42} *right1 = {17} **mergeSort(array2 = left1) -- Exit immediately **mergeSort(array3 = right1) -- Exit immediately **merge(result = array1, left = left1, right = right1) -- result.length = 2 *mergeSort(array4 = right0) *left2 = {33} *right2 = {55} **mergeSort(array5 = left2) -- Exit immediately **mergeSort(array6 = right2) -- Exit immediately **merge(result = array4, left = left2, right = right2) -- result.length = 2 merge(result = array0, left = left0, right = right0) -- result.length = 4```

I think you are confused with what array is being sent as the result parameter to the merge method when recursively checking each half of the array. The result parameter is the array before it was split into left and right, not after, so the length of the result array parameter can never be less than 2.