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

As you will see, we can use these observations in two ways. First, we can ascertain the algorithm's
efficiency. Second, we can formulate the mergeSort algorithm iteratively.

Note: Merge sort rearranges the entries in an array during its merge steps.

Question 1 Trace the steps that a merge sort takes when sorting the following array into
ascending order: 9 6 2 4 8 7 5 3.

9.5

Implementation note. Although the implementation of the recursive mergesort is straightforward,
you should be careful to allocate the temporary array only once. Since the array is an implementa-
tion detail, you might be tempted to hide its allocation in the method merge . But since merge is
called each time mergesort is called recursively, a temporary array would be allocated and initial-
ized many times. Instead, we can allocate a temporary array in the following public version of
mergesort and pass it to a private mergesort that implements the pseudocode given previously:
public static <T extends Comparable<? super T>>
void mergeSort(T[] a, int first, int last)

{

// the cast is safe because the new array contains null entries
@SuppressWarnings("unchecked")
T[] tempArray = (T[]) new Comparable<?>[a.length]; // unchecked cast
mergeSort(a, tempArray, first, last);
} // end mergeSort
Segment 8.2 in the previous chapter introduced the notation ? super T to mean any superclass of T .
When we allocate an array of Comparable objects, we use a wildcard ? to represent any object. We
then cast the array to an array of type T objects.

The Efficiency of Merge Sort
9.6

Assume for now that n is a power of 2, so that we can divide n by 2 evenly. The array in Figure 9-3
has n = 8 entries. The initial call to mergeSort makes two recursive calls to mergeSort , dividing the
array into two subarrays of n / 2, or 4, entries each. Each of the two recursive calls to mergeSort
makes two recursive calls to mergeSort , dividing the two subarrays into four subarrays of n / 2 2 , or 2,
entries each. Finally, recursive calls to mergeSort divide the four subarrays into eight subarrays of
n / 2 3 , or 1, entry each. It takes three levels of recursive calls to obtain subarrays of one entry each.
Notice that the original array contained 2 3 entries. The exponent 3 is the number of levels of recursive
calls. In general, if n is 2 k , k levels of recursive calls occur.
Now consider the merge steps, because that is where the real work occurs. The merge step
makes at most n - 1 comparisons among the n entries in the two subarrays. Figure 9-4 provides an
example of a merge that requires n - 1 comparisons, while Figure 9-1 shows an example where
fewer than n - 1 comparisons occur. Each merge also requires n moves to a temporary array and n
moves back to the original array. In total, each merge requires at most 3 n - 1 operations.
Each call to mergeSort calls merge once. The merge operation as a result of the original call to
mergeSort requires at most 3 n - 1 operations. It is O( n ). An example of this merge appears as step 21 in
Figure 9-3. The two recursive calls to mergeSort result in two calls to merge . Each call merges n / 2
entries in at most 3 n / 2 - 1 operations. The two merges then require at most 3 n - 2 operations. They
are O( n ). The next level of recursion involves 2 2 calls to mergeSort resulting in four calls to merge .
Each call to merge merges n / 2 2 entries in at most 3 n / 2 2 - 1 operations. Together these four merges use
at most 3 n - 2 2 operations, so are O( n ).