UML and Patterns - Absolute Java - page 703

Display 12.8 Quick Sort Realization of Sorting Pattern (part 3 of 3)

50 a[begin + i] = temp[i];
51 return (begin + up);

52 }

53 private static void join( double [] a, int begin,

54 int splitPoint, int end)

55 {
56

//Nothing to do.

57 }

58 }

Restrictions on the Sorting Pattern
The sorting pattern, like all patterns, has some restrictions on where it applies.
As we formulated the sorting pattern, it applies only to types for which the
< operator is defined. Also, it applies only to sorting into increasing order; it
does not apply to sorting into decreasing order. However, this is a result of our
simplifying details to make the presentation clearer. You can make the pattern
more general by replacing the < operator with a boolean valued method called
compare that has two arguments of the base type of the array, which returns true
or false depending on whether the first “comes before” the second. Then, the
only restriction is that the compare method must have a reasonable definition. 1
This sort of generalization is discussed in Chapter 13 in the subsection entitled
“The Comparable Interface.”

Efficiency of the Sorting Pattern ★
Essentially any sorting algorithm can be realized using this sorting pattern. However,
the most efficient implementations are those for which the split method divides the
array into two substantial size chunks, such as half-and-half, or one-fourth and three-
fourths. A realization of split that divides the array into one or a very few elements
and the rest of the array will not be very efficient.
For example, the merge sort realization of split divides the array into two roughly
equal parts, and merge sort is indeed very efficient. It can be shown (although we will
not do so here) that merge sort has a worst-case running time that is the best possible
“up to an order of magnitude.”

1 The technical requirement is that the compare method be a total ordering , a concept discussed in
Chapter 13 . Essentially, all common orderings that you might want to sort by are total orderings.

The Comparable interface has a method compareTo , which is slightly different from compare .
However, the method we described as compare can easily be defined using the method compareTo
as a helping method.