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

for (int i = 0; i < result.length; i++) {
if (i2 >= right.length || (i1 < left.length &&
left[i1] <= right[i2])) {
result[i] = left[i1]; // take from left
i1++;
} else {
result[i] = right[i2]; // take from right
i2++;
}
}
}
Recursive Merge Sort
We've written the code to split an array into halves and to merge the sorted halves
into a sorted whole. The overall merge sort method now looks like this:
public static void mergeSort(int[] a) {
// split array into two halves
int[] left = Arrays.copyOfRange(a, 0, a.length / 2);
int[] right = Arrays.copyOfRange(a, a.length / 2, a.length);
// sort the two halves
...
// merge the sorted halves into a sorted whole
merge(a, left, right);
}
The last piece of our program is the code to sort each half of the array. How can
we sort the halves? We could call the selectionSort method created earlier in this
chapter on the two halves. But in the previous chapter we discussed the recursive
“leap of faith,” the belief that our own method will work properly to solve a smaller
version of the same problem. In this case, a better approach is to merge sort the two
smaller halves. We can recursively call our own mergeSort method on the array
halves, and if it's written correctly, it'll put each of them into sorted order. Our origi-
nal pseudocode can now be rewritten as the following pseudocode:
split the array into two halves.
merge sort the left half.
merge sort the right half.
merge the two halves.
If we're making our merge sort algorithm recursive, it needs to have a base case
and a recursive case. The preceding pseudocode specifies the recursive case, but for
the base case, what are the simplest arrays to sort? An array with either no elements