Faster Sorting Methods - Data Structures and Abstractions with Java - page 219

Recursive Merge Sort
9.3

The algorithm. In a merge sort, you merge two sorted arrays that are actually halves of the original
array. That is, you divide the array into halves, sort each half, and merge the sorted halves into a second
temporary array, as Figure 9-2 shows. You then copy the temporary array back to the original array.

FIGURE 9-2

The major steps in a merge sort

7 5 9 3 6 0 2 4 Divide the array into two halves

0 1 2 3 4 5 6 7

3 5 7 4 6 Sort the two halves

9 0 2

Merge the sorted halves into
another array

0 3

2 4 5 6 7 9

Copy the merged array back into
the original array

0 2 3 4 5 6 7 9

This sounds like a simple plan, but how did we sort the two halves of the array? By using a
merge sort, of course! If mid is the index of the approximate midpoint of an array of n entries, we
need to sort the entries indexed by 0 through mid , and then the entries indexed by mid + 1 through
n - 1 . Since we perform these sorts by making recursive calls to the merge sort algorithm, the algo-
rithm needs two parameters— first and last —to specify the first and last indices of the subrange
of the array to be sorted. We will use the notation a[first..last] to mean the array entries
a[first] , a[first + 1] , ..., a[last] .
Merge sort has the following recursive formulation:
Algorithm mergeSort(a, tempArray, first, last)
// Sorts the array entries a[first] through a[last] recursively.

if (first < last)
{

mid = (first + last) / 2
mergeSort(a, tempArray, first, mid)
mergeSort(a, tempArray, mid + 1, last)
Merge the sorted halves a[first..mid] and a[mid + 1..last] using the array tempArray

}

Notice that the algorithm ignores arrays of one or fewer entries.
The following pseudocode describes the merge step:
Algorithm merge(a, tempArray, first, mid, last)
// Merges the adjacent subarrays a[first..mid] and a[mid + 1..last] .

beginHalf1 = first
endHalf1 = mid
beginHalf2 = mid + 1
endHalf2 = last

// While both subarrays are not empty, compare an entry in one subarray with
// an entry in the other; then copy the smaller item into the temporary array
index = 0 // next available location in tempArray