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

or just one element doesn't need to be sorted at all. At least two elements must
be present in order for them to appear in the wrong order, so the simple case would
be an array with a length less than 2. This means that our final pseudocode for the
merge sort method is the following:
if (array length is more than 1) {
split the array into two halves.
merge sort the left half.
merge sort the right half.
merge the two halves.
}
No else case is needed because if the array size is 0 or 1, we don't need to do
anything to the array. This recursive algorithm has an empty base case.
The following method implements the complete merge sort algorithm:
// Places the elements of the given array into sorted order
// using the merge sort algorithm.
// post: array is in sorted (nondecreasing) order
public static void mergeSort(int[] a) {
if (array.length > 1) {
// split array into two halves
int[] left = Arrays.copyOfRange(a, 0, a.length / 2);
int[] right = Arrays.copyOfRange(a, a.length / 2, a.length);
// recursively sort the two halves
mergeSort(left);
mergeSort(right);
// merge the sorted halves into a sorted whole
merge(a, left, right);
}
}
To get a better idea of the algorithm in action, we'll temporarily insert a few
println statements into its code and run the method on the eight-element sample
array shown previously in this section. We'll insert the following println statement
at the start of the mergeSort method:
// at start of mergeSort method
System.out.println("sorting " + Arrays.toString(array));
We'll also put the following println statement at the start of the merge method:
// at start of merge method
System.out.println("merging " + Arrays.toString(left) +
" and " + Arrays.toString(right));