Java Reference
In-Depth Information
too much time. This chapter presents sorting algorithms that are much faster in general than the
methods in Chapter 8.
9.1
The
merge sort
divides an array into halves, sorts the two halves, and then merges them into one sorted
array. The algorithm for merge sort is usually stated recursively. You know that a recursive algorithm
expresses the solution to a problem in terms of a smaller version of the same problem. When you divide
a problem into two or more smaller but
distinct
problems, solve
each
new problem, and then combine
their solutions to solve the original problem, the strategy is said to be a
divide and conquer
algorithm.
That is, you divide the problem into pieces and conquer each piece to reach a solution. Although divide
and conquer algorithms often are expressed recursively, this is not a requirement.
When expressed recursively, a divide and conquer algorithm contains two or more recursive
calls. Most of the recursive solutions that you have seen so far do not use the divide and conquer strat-
egy. For example, Segment 8.7 gave a recursive version of the selection sort. Even though that algo-
rithm considers smaller and smaller arrays, it does not divide the problem into two sorting problems.
The real effort during the execution of a merge sort occurs during the merge step, and this is
also the step that involves most of the programming effort, so we will begin there.
VideoNote
Merge sort
9.2
Imagine that you have two distinct arrays that are sorted. Merging two sorted arrays is not difficult,
but it does require an additional array. Processing both arrays from beginning to end, you compare
an entry in one array with an entry in the other and copy the smaller entry to a new third array, as
Figure 9-1 shows. After reaching the end of one array, you simply copy the remaining entries from
the other array to the new third array.
FIGURE 9-1
Merging two sorted arrays into one sorted array
First array
Second array
3
5
7
9
0
2
4
6
3
0, so copy 0 to new array
0
5
3
7
9
0
2
4
6
2
3
2, so copy 2 to new array
3
3
5
7
9
0
2
4
6
4
3
4, so copy 3 to new array
New merged array
5
3
5
7
9
0
2
4
6
6
5
4, so copy 4 to new array
7
3
5
7
9
0
2
4
6
5
6, so copy 5 to new array
9
3
5
7
9
0
2
4
6
7
6, so copy 6 to new array
3 5
7 9
0 2 4 6
The entire second array has been copied to the new array
Copy the rest of the first array to the new array
