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
{
The method
sort
is identical to the version in the
pattern (Display 12.5) except that
Type
is replaced
with
double
.
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
}
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)
