Java Reference
In-Depth Information
Display 12.6
Merge Sort Realization of Sorting Pattern
(part 2 of 2)
42
else
43
{
44
temp[i] = a[nextRight];
45
i++; nextRight++;
46
}
47
}
48
while
(nextLeft <= splitPoint)
//Copy rest of left chunk, if any.
49
{
50
temp[i] = a[nextLeft];
51
i++; nextLeft++;
52
}
53
while
(nextRight <= end)
//Copy rest of right chunk, if any.
54
{
55
temp[i] = a[nextRight];
56
i++; nextRight++;
57
}
58
for
(i = 0; i < intervalSize; i++)
59
a[begin + i] = temp[i];
60
}
61
}
EXAMPLE:
(continued)
splitting value are at the other end of the array, and the splitting value is placed so that it
divides the entire array into these smaller and larger elements. Note that the smaller ele-
ments are not sorted and the larger elements are not sorted, but all the elements before
the splitting value are smaller than any of the elements after the splitting value. The
smaller elements are sorted by a recursive call, the larger elements are sorted by another
recursive call, and then these two sorted segments are combined with the
join
method.
In this case, the
join
method is as simple as it could be. It does nothing. Since the sorted
smaller elements all precede the sorted larger elements, the entire array is sorted.
A demonstration program for the quick sort method
sort
in Display 12.8 is given in
the file
QuickSortDemo.java
on the accompanying CD.
(Both the merge sort and the quick sort realizations can be done without the use of
a second temporary array,
temp
. However, that detail would only distract from the
message of this example. In a real application, you may or may not, depending on
details, want to consider the possibility of doing a sort realization without the use of
the temporary array.)
