Java Reference
In-Depth Information
in
list2
. Finally, all the elements in one of the lists are moved to
temp
. If there are still
unmoved elements in
list1
, copy them to
temp
(lines 35-36). If there are still unmoved ele-
ments in
list2
, copy them to
temp
(lines 38-39).
Figure 23.5 illustrates how to merge the two arrays
list1
(2 4 5 9) and
list2
(1 6 7 8).
Initially the current elements to be considered in the arrays are 2 and 1. Compare them and
move the smaller element 1 to
temp
, as shown in Figure 23.5a.
current2
and
current3
are increased by 1. Continue to compare the current elements in the two arrays and move the
smaller one to
temp
until one of the arrays is completely moved. As shown in Figure 23.5b,
all the elements in
list2
are moved to
temp
and
current1
points to element 9 in
list1
.
Copy 9 to
temp
, as shown in Figure 23.5c.
merge animation on
Companion Website
current1
current2
current1
current2
current1
current2
2
4
5
9
1
6
7
8
2
4
5
9
1
6
7
8
2
4
5
9
1
6
7
8
1
12
4
5
6
7
8
12
4
5
6
7
8
9
current3
current3
current3
(a) After moving
1
to
temp
(b) After moving all the
elements in
list2
to
temp
(c) After moving 9 to
temp
F
IGURE
23.5
Two sorted arrays are merged into one sorted array.
The
mergeSort
method creates two temporary arrays (lines 6, 12) during the divid-
ing process, copies the first half and the second half of the array into the temporary arrays
(lines 7, 13), sorts the temporary arrays (lines 8, 15), and then merges them into the original
array (line 18), as shown in Figure 23.6a. You can rewrite the code to recursively sort the first
half of the array and the second half of the array without creating new temporary arrays, and
then merge the two arrays into a temporary array and copy its contents to the original array, as
shown in Figure 23.6b. This is left for you to do in Programming Exercise 23.20.
Original list
Original list
Divide
Divide
Copy first half
Copy second half
firstHalf
(temporary array)
secondHalf
(temporary array)
Sort first half of
the original array
Sort second half of
the original array
Recursive sort
Recursively sort
Merge
Merge
Copy this to the
original list
Merge to list
New sorted list
New sorted temporary list
(a)
(b)
F
IGURE
23.6
Temporary arrays are created to support a merge sort.
Note
A merge sort can be implemented efficiently using parallel processing. See Section 30.16,
Parallel Programming, for a parallel implementation of a merge sort.
Search WWH ::
Custom Search