Sorting algorithms - Data Structures and Problem Solving Using Java - page 364

1 /**
2 * Mergesort algorithm.
3 * @param a an array of Comparable items.
4 */
5 public static <AnyType extends Comparable<? super AnyType>>
6 void mergeSort( AnyType [ ] a )
7 {
8 AnyType [ ] tmpArray = (AnyType []) new Comparable[ a.length ];
9 mergeSort( a, tmpArray, 0, a.length - 1 );
10 }
11
12 /**
13 * Internal method that makes recursive calls.
14 * @param a an array of Comparable items.
15 * @param tmpArray an array to place the merged result.
16 * @param left the left-most index of the subarray.
17 * @param right the right-most index of the subarray.
18 */
19 private static <AnyType extends Comparable<? super AnyType>>
20 void mergeSort( AnyType [ ] a, AnyType [ ] tmpArray,
21 int left, int right )
22 {
23 if( left < right )
24 {
25 int center = ( left + right ) / 2;
26 mergeSort( a, tmpArray, left, center );
27 mergeSort( a, tmpArray, center + 1, right );
28 merge( a, tmpArray, left, center + 1, right );
29 }
30 }

figure 8.8
Basic mergeSort routines

types in Java. An alternative algorithm is quicksort, which we describe in the
next section. Quicksort is the algorithm used in C++ to sort all types, and it is
used in java.util.Arrays.sort to sort arrays of primitive types.

quicksort

8.6

As its name implies, quicksort is a fast divide-and-conquer algorithm. Its
average running time is O ( N log N ). Its speed is mainly due to a very tight
and highly optimized inner loop. It has quadratic worst-case performance,
which can be made statistically unlikely to occur with a little effort. On
the one hand, the quicksort algorithm is relatively simple to understand
and prove correct because it relies on recursion. On the other hand, it is a
tricky algorithm to implement because minute changes in the code can

When properly
implemented ,
quicksort is a fast
divide-and-
conquer algorithm.