Java Reference
In-Depth Information
The merge sort algorithm can be described recursively as follows: The algorithm
divides the array into two halves and applies a merge sort on each half recursively.
After the two halves are sorted, merge them.
Key
Point
merge sort
The algorithm for a merge sort is given in Listing 23.5.
L
ISTING
23.5
Merge Sort Algorithm
1
public static void
mergeSort(
int
[] list) {
2
if
(list.length >
1
) {
3 mergeSort(list[
0
... list.length /
2
]);
4 mergeSort(list[list.length /
2
+
1
... list.length]);
5 merge list[
0
... list.length /
2
] with
6 list[list.length /
2
+
1
... list.length];
7 }
8 }
base condition
sort first half
sort second half
merge two halves
Figure 23.4 illustrates a merge sort of an array of eight elements (2 9 5 4 8 1 6 7). The original
array is split into (2 9 5 4) and (8 1 6 7). Apply a merge sort on these two subarrays recursively
to split (2 9 5 4) into (2 9) and (5 4) and (8 1 6 7) into (8 1) and (6 7). This process continues
until the subarray contains only one element. For example, array (2 9) is split into the subar-
rays (2) and (9). Since array (2) contains a single element, it cannot be further split. Now
merge (2) with (9) into a new sorted array (2 9); merge (5) with (4) into a new sorted array
(4 5). Merge (2 9) with (4 5) into a new sorted array (2 4 5 9), and finally merge (2 4 5 9) with
(1 6 7 8) into a new sorted array (1 2 4 5 6 7 8 9).
merge sort illustration
2
94
5
8167
split
294
8167
split
divide
29
54
81
6 7
split
2
9
5
4
8
1
6
7
merge
29
45
1
8
67
conquer
merge
249
178
6
merge
1
25
4
6789
F
IGURE
23.4
Merge sort employs a divide-and-conquer approach to sort the array.
The recursive call continues dividing the array into subarrays until each subarray contains
only one element. The algorithm then merges these small subarrays into larger sorted subar-
rays until one sorted array results.
The merge sort algorithm is implemented in Listing 23.6.
L
ISTING
23.6
MergeSort.java
1
public class
MergeSort {
2
/** The method for sorting the numbers */
3
public static void
mergeSort(
int
[] list) {
4
if
(list.length >
1
) {
base case
Search WWH ::
Custom Search