Java Reference
In-Depth Information
Suppose the algorithm has already merged smaller arrays to create sorted arrays A:
4 10 34 56 77
and B:
5 30 51 52 93
Merge sort combines these two arrays into one larger, sorted array. The smallest element
in A is 4 (located in the zeroth index of A). The smallest element in B is 5 (located in the
zeroth index of B). In order to determine the smallest element in the larger array, the al-
gorithm compares 4 and 5. The value from A is smaller, so 4 becomes the first element in
the merged array. The algorithm continues by comparing 10 (the second element in A) to
5 (the first element in B). The value from B is smaller, so 5 becomes the second element
in the larger array. The algorithm continues by comparing 10 to 30, with 10 becoming
the third element in the array, and so on.
Figure 19.6 declares the
MergeSortTest
class, which contains:
•
static
method
mergeSort
to initiate the sorting of an
int
array using the merge
sort algorithm
•
static
method
sortArray
to perform the recursive merge sort algorithm—this
is called by method
mergeSort
•
static
method
merge
to merge two sorted subarrays into a single sorted subarray
•
static
method
subarrayString
to get a subarray's
String
representation for
output purposes, and
•
main
to test method
mergeSort
.
Method
main
(lines 101-116) is identical to
main
in Figs. 19.4-19.5 except that line 112
calls method
mergeSort
. The output from this program displays the splits and merges per-
formed by merge sort, showing the progress of the sort at each step of the algorithm. It's
well worth your time to step through these outputs to fully understand this elegant sorting
algorithm.
1
// Fig. 19.6: MergeSortTest.java
2
// Sorting an array with merge sort.
3
import
java.security.SecureRandom;
4
import
java.util.Arrays;
5
6
public class
MergeSortTest
7
{
8
// calls recursive split method to begin merge sorting
9
public static void
mergeSort(
int
[] data)
10
{
11
sortArray(data,
0
, data.length -
1
);
// sort entire array
12
}
// end method sort
13
Fig. 19.6
|
Sorting an array with merge sort. (Part 1 of 5.)
