UML and Patterns - Absolute Java - page 697

We have presented the Model-View-Controller pattern as if the user is the Controller,
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 hardware 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
collection 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 , it 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
intervals 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 splitPoint and the points after splitPoint , with no rearranging. Display 12.6
realizes the sorting pattern by defining split this way. On the other hand, the method
split could do something more elaborate such as 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 in Display 12.8
that realizes the sorting pattern in this second way.
(continued)