Searching and Sorting - Building Java Programs: A Back to Basics Approach - page 806

The following code is an initial attempt to implement the merge algorithm that
was just described:
// initial incorrect attempt
public static void merge(int[] result, int[] left, int[] right) {
int i1 = 0; // index into left array
int i2 = 0; // index into right array
for (int i = 0; i < result.length; i++) {
if (left[i1] <= right[i2]) {
result[i] = left[i1]; // take from left
i1++;
} else {
result[i] = right[i2]; // take from right
i2++;
}
}
}
The preceding code is incorrect and will cause an out-of-bounds exception. After
the program completes the seventh step of the preceding diagram, all of the elements
in the left subarray will have been consumed and the left index i1 will run off the
end of the subarray. Then, when the code tries to access element left[i1] , it will
crash. A similar problem would occur if the right index i2 exceeded the bounds of
the right array.
We need to modify our code to remain within the bounds of the arrays. The
if/else logic needs to ensure that the index i1 or i2 is within the array bounds
before the program attempts to access the appropriate element. The simple test in the
pseudocode needs to be expanded:
if (i2 has passed the end of the right array, or
left element at i1 < right element at i2) {
take from left.
} else {
take from right.
}
The following second version of the code correctly implements the merging behavior.
The preconditions and postconditions of the method are documented in comments:
// Merges the given left and right arrays into the given
// result array. Second, working version.
// pre : result is empty; left/right are sorted
// post: result contains result of merging sorted lists.
public static void merge(int[] result, int[] left, int[] right) {
int i1 = 0; // index into left array
int i2 = 0; // index into right array