UML and Patterns - Java - page 639

We have presented the Model-View-Controller pattern as if the user were the Con-
troller. That was done primarily to simplify the examples. The Controller need not be
under the direct control of the user, but could be some other kind of software or hard-
ware component.
EXAMPLE: A Sorting Pattern
The most efficient sorting algorithms all seem to follow a similar pattern. Expressed
recursively, they divide the list of elements to be sorted into two smaller lists, recursively
sort the two smaller lists, and then recombine the two sorted lists to obtain the final
sorted list. In Display 12.5 this pattern is expressed as pseudocode (in fact, almost correct
Java code) for a method to sort an array into increasing order using the < operator.
Our sorting pattern uses a divide-and-conquer strategy. It divides the entire collec-
tion of elements to be sorted into two smaller collections, sorts the smaller collections
by recursive calls, and then combines the two sorted collections to obtain the final
sorted array. The following is the heart of our sorting pattern:
int splitPoint = split(a, begin, end);
sort(a, begin, splitPoint);
sort(a, splitPoint + 1, end);
join(a, begin, splitPoint, end);
Although the pattern does impose some minimum requirements on the methods
split and join , the pattern does not say exactly how the methods split and join
are defined. Different definitions of split and join will yield different sorting
algorithms.
The method split rearranges the elements in the interval a[begin] through
a[end] and divides the rearranged interval at a split point, splitPoint . The two
smaller intervals a[begin] through a[splitPoint] and [splitPoint + 1] through
a[end] are then sorted by a recursive call to the method sort . Note that the split
method both rearranges the elements in the array interval a[begin] through a[end]
and returns the index splitPoint that divides the interval. After the two smaller inter-
vals are sorted, the method join then combines the two sorted intervals to obtain the
final sorted version of the entire larger interval.
The pattern says nothing about how the method split rearranges and divides the
interval a[begin] through a[end] . In a simple case, split might simply choose a value
splitPoint between begin and end and divide the interval into the points before split-
Point and the points after splitPoint , with no rearranging. We will see an example that
realizes the sorting pattern by defining split this way. On the other hand, the method
split could do something more elaborate like move all the “small” elements to the
front of the array and all the “large” elements toward the end of the array. This would be
a step on the way to fully sorting the values. We will also see an example that realizes the
sorting pattern in this second way.
(continued)