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

1 /**
2 * Internal method that merges two sorted halves of a subarray.
3 * @param a an array of Comparable items.
4 * @param tmpArray an array to place the merged result.
5 * @param leftPos the left-most index of the subarray.
6 * @param rightPos the index of the start of the second half.
7 * @param rightEnd the right-most index of the subarray.
8 */
9 private static <AnyType extends Comparable<? super AnyType>>
10 void merge( AnyType [ ] a, AnyType [ ] tmpArray,
11 int leftPos, int rightPos, int rightEnd )
12 {
13 int leftEnd = rightPos - 1;
14 int tmpPos = leftPos;
15 int numElements = rightEnd - leftPos + 1;
16
17 // Main loop
18 while( leftPos <= leftEnd && rightPos <= rightEnd )
19 if( a[ leftPos ].compareTo( a[ rightPos ] ) <= 0 )
20 tmpArray[ tmpPos++ ] = a[ leftPos++ ];
21 else
22 tmpArray[ tmpPos++ ] = a[ rightPos++ ];
23
24 while( leftPos <= leftEnd ) // Copy rest of first half
25 tmpArray[ tmpPos++ ] = a[ leftPos++ ];
26
27 while( rightPos <= rightEnd ) // Copy rest of right half
28 tmpArray[ tmpPos++ ] = a[ rightPos++ ];
29
30 // Copy tmpArray back
31 for( int i = 0; i < numElements; i++, rightEnd-- )
32 a[ rightEnd ] = tmpArray[ rightEnd ];
33

figure 8.9
The merge routine

}

make significant differences in running time. We first describe the algo-
rithm in broad terms. We then provide an analysis that shows its best-,
worst-, and average-case running times. We use this analysis to make deci-
sions about how to implement certain details in Java, such as the handling
of duplicate items.
Consider the following simple sorting algorithm to sort a list: arbitrarily
choose any item, and then form three groups: those smaller than the chosen
item, those equal to the chosen item, and those larger than the chosen item.
Recursively sort the first and third groups, and then concatenate the three
groups. The result is guaranteed to be a sorted arrangement of the original
list (we will verify this soon). A direct implementation of this algorithm is
shown in Figure 8.10, and its performance is generally speaking, quite
respectable on most inputs. In fact, if the list contains large numbers of