Java Reference
In-Depth Information
9
int
[] a = ArrayUtil.randomIntArray(
20
,
100
);
10 System.out.println(Arrays.toString(a));
11 MergeSorter sorter =
new
MergeSorter(a);
12 sorter.sort();
13 System.out.println(Arrays.toString(a));
14 }
15 }
Typical Output
[8, 81, 48, 53, 46, 70, 98, 42, 27, 76, 33, 24, 2,
76, 62, 89, 90, 5, 13, 21]
[2, 5, 8, 13, 21, 24, 27, 33, 42, 46, 48, 53, 62,
70, 76, 76, 81, 89, 90, 98]
S
ELF
C
HECK
7.
Why does only one of the two arraycopy calls at the end of the
merge
method do any work?
8.
Manually run the merge sort algorithm on the array 8 7 6 5 4 3 2 1.
14.5 Analyzing the Merge Sort Algorithm
The merge sort algorithm looks a lot more complicated than the selection sort
algorithm, and it appears that it may well take much longer to carry out these repeated
subdivisions. However, the timing results for merge sort look much better than those
for selection sort (see table on next page).
Figure 2
shows a graph comparing both sets of performance data. That is a
tremendous improvement. To understand why, let us estimate the number of array
element visits that are required to sort an array with the merge sort algorithm. First,
let us tackle the merge process that happens after the first and second halves have
been sorted.
Each step in the merge process adds one more element to
a
. That element may come
from
first
or
second
, and in most cases the elements from the two halves must
be compared to see which one to take. Let us count that as 3 visits (one for a and one
each for
first
and
second
) per element, or 3n visits total, where n denotes the
