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

The following pseudocode provides the basic idea of the merge sort algorithm:
split the array into two halves.
sort the left half.
sort the right half.
merge the two halves.
Let's look at splitting the array and merging halves first; then we'll talk about
the sorting.
Splitting and Merging Arrays
Splitting one array into its two halves is relatively straightforward. We'll set a
midpoint at one half of the length of the array and consider everything before this
midpoint to be part of the “left” half and everything that follows it to be in the “right”
half. We can use the method Arrays.copyOfRange to extract the halves of an array
as new arrays. The “left” half is from range 0 to half the length, and the “right” half is
from half the length to the full length:
// split array into two halves
int[] left = Arrays.copyOfRange(a, 0, a.length / 2);
int[] right = Arrays.copyOfRange(a, a.length / 2, a.length);
We will need to sort these left/right halves, then merge them into a sorted whole.
For now, let's think about how we would merge two sorted subarrays. (We'll come
back to sorting them later.) Suppose that you have two stacks of exam papers, each
sorted alphabetically by name, and you need to combine them into a single stack
sorted by name. The simplest algorithm is to place both stacks in front of you, look at
the top paper of each stack, pick up the paper that comes first in alphabetical order,
and put it face down into a third pile. You then repeat this process, comparing the
papers on the top of each stack and placing the one that comes first face down on the
merged stack, until one of your two original stacks is empty. Once one is empty, you
just grab the entire remaining stack and place it on your merged pile.
The idea behind merging two sorted arrays is similar, except that instead of physi-
cally removing papers (integers) from the piles (subarrays), we'll keep an index for
each subarray and increment that index as we process a given element. Here is a
pseudocode description of the merging algorithm:
i1 = 0. // left index
i2 = 0. // right index
for (number of elements in entire array) {
if (left value at i1 < right value at i2) {
include value from left array in new array.
i1++;
} else {
include value from right array in new array.