Java Reference
In-Depth Information
Let us write a
MergeSorter
class that implements this idea. When the
MergeSorter
sorts an array, it makes two arrays, each half the size of the original,
and sorts them recursively. Then it merges the two sorted arrays together:
public void sort()
{
if (a.length <= 1) return;
int[] first = new int[a.length / 2];
int[] second = new int [a.length - first.length];
System.arraycopy(a, 0, first, 0, first.length);
System.arraycopy(a,
first.length, second, 0, second.length);
MergeSorter firstSorter = new MergeSorter(first);
MergeSorter secondSorter = new
MergeSorter(second);
firstSorter.sort();
secondSorter.sort();
merge(first, second);
}
The
merge
method is tedious but quite straightforward. You will find it in the code
that follows.
ch14/mergesort/MergeSorter.java
1 /**
2
This class sorts an array, using the merge sort algorithm.
3 */
4
public class
MergeSorter
5 {
6 /**
7
Constructs a merge sorter.
8 @param anArray
the array to sort
9 */
10
public
MergeSorter(
int
[] anArray)
11 {
12 a = anArray;
13 }
14
15 /**
16
Sorts the array managed by this merge sorter.
