Java Reference
In-Depth Information
Display 12.6
Merge Sort Realization of Sorting Pattern
(part 1 of 2)
1 /**
2
Class that realizes the divide-and-conquer sorting pattern and
3
uses the merge sort algorithm.
4*/
5
public class
MergeSort
6 {
7 /**
8
Precondition: Interval a[begin] through a[end] of a have elements.
9
Postcondition: The values in the interval have
10
been rearranged so that a[begin]
< =
a[begin
+
1]
< =
. . .
< =
a[end]
.
11 */
12
public static void
sort(
double
[] a,
int
begin,
int
end)
13 {
14
if
((end — begin) >= 1)
15 {
16
int
splitPoint = split(a, begin, end);
17 sort(a, begin, splitPoint);
18 sort(a, splitPoint + 1, end);
19 join(a, begin, splitPoint, end);
20 }
//else sorting one (or fewer) elements so do nothing.
21 }
The method
sort
is identical to the version in
the pat ern (Display 12.5) except that
Type
is
replaced with
double.
22
private static int
split(
double
[] a,
int
begin,
int
end)
23 {
24
return
((begin + end)/2);
25 }
26
private static void
join(
double
[] a,
int
begin,
int
splitPoint,
int
end)
27 {
28
double
[] temp;
29
int
intervalSize = (end - begin + 1);
30 temp =
new double
[intervalSize];
31
int
nextLeft = begin;
//index for first chunk
32
int
nextRight = splitPoint + 1;
//index for second chunk
33
int
i = 0;
//index for temp
34
//Merge till one side is exhausted:
35
while
((nextLeft <= splitPoint) && (nextRight <= end))
36 {
37
if
(a[nextLeft] < a[nextRight])
38 {
39 temp[i] = a[nextLeft];
40 i++; nextLeft++;
41 }
(continued)