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)
than the 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 elements 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. Because 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 website.
(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.)
