Java Reference
In-Depth Information
=
4 [2
t
(1)
+
2]
+
8
+
8
=
8
+
8
+
8
=
8
×
3
Since 8
=
2
3
, 3
=
log
2
8, so we guess that
t
(
n
)
=
n
log
2
n
Just as we did in Chapter 7, we now need to prove that our guess is in fact true. We leave this proof
as an exercise.
Once we have the merge algorithm, developing the recursive merge sort is easy. Developing an itera-
tive merge sort is not as simple. We begin by making some observations about the recursive solution.
The recursive calls simply divide the array into
n
one-entry subarrays, as you can see in
Figure 9-3. Although we do not need recursion to isolate the entries in an array, the recursion con-
trols the merging process. To replace the recursion with iteration, we will need to control the
merges. Such an algorithm will be more efficient of both time and space than the recursive algo-
rithm, since it will eliminate the recursive calls and, therefore, the stack of activation records. But
an iterative merge sort will be trickier to code without error.
Basically, an iterative merge sort starts at the beginning of the array and merges pairs of indi-
vidual entries to form two-entry subarrays. Then it returns to the beginning of the array and merges
pairs of the two-entry subarrays to form four-entry subarrays, and so on. However, after merging all
pairs of subarrays of a particular length, we might have entries left over. Merging these requires
some care. Project 2 at the end of this chapter asks you to develop an iterative merge sort. You will
see there that you can save much of the time necessary to copy the temporary array back to the orig-
inal array during the merges.
The class
Arrays
in the package
java.util
defines several versions of a static method
sort
to sort
an array into ascending order. For an array of objects,
sort
uses a merge sort. The method
public static void
sort(Object[] a)
sorts an entire array
a
of objects, while the method
public static void
sort(Object[] a,
int
first,
int
after)
sorts the objects in
a[first]
through
a[after - 1]
. For both methods, objects in the array must
define the
Comparable
interface.
The merge sort used by these methods skips the merge step if none of the entries in the left half
of the array are greater than the entries in the right half. Since both halves are sorted already, the
merge step is unnecessary in this case.
Note:
Stable sorts
A sorting algorithm is
stable
if it does not change the relative order of objects that are equal.
For example, if object
x
appears before object
y
in a collection of data, and
x.compareTo(y)
is zero, a stable sorting algorithm will leave object
x
before object
y
after sorting the data.
Stability is important to certain applications. For example, suppose that you sort a group of
people, first by name and then by age. A stable sorting algorithm will ensure that people of
the same age will remain in alphabetical order.
The merge sorts in the Java Class Library are stable. Exercise 10 at the end of this chapter
asks you to identify the stable sorting algorithms presented in this chapter and the previous one.
