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)
 
Search WWH ::




Custom Search