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

Finally, the remainder of the B array is copied to C:

1 13 24 26 2 15 27 38

1 2 13 15 24 26 27 38

Actr Bctr

Cctr

The time needed to merge two sorted arrays is linear because each com-
parison advances Cctr (thus limiting the number of comparisons). As a result,
a divide-and-conquer algorithm that uses a linear merging procedure runs in
O ( N log N ) worst-case time. This running time also represents the average-
case and best-case times because the merging step is always linear.
An example of the mergesort algorithm would be sorting the 8-element
array 24, 13, 26, 1, 2, 27, 38, 15. After recursively sorting the first four and
last four elements, we obtain 1, 13, 24, 26, 2, 15, 27, 38. Then we merge the
two halves, obtaining the final array 1, 2, 13, 15, 24, 26, 27, 38.

8.5.2 the mergesort algorithm

A straightforward implementation of mergesort is shown in Figure 8.8. The
one-parameter, nonrecursive mergeSort is a simple driver that declares a tempo-
rary array and calls recursive mergeSort with the boundaries of the array. The
merge routine follows the description given in Section 8.5.1. It uses the first half
of the array (indexed from left to center ) as A, the second half (indexed from
center+1 to right ) as B, and the temporary as C . Figure 8.9 implements the
merge routine. The temporary is then copied back into the original array.

Mergesort uses lin-
ear extra memory,
which is a practical
liability.

Although mergesort's running time is O ( N log N ) , it has the significant
problem that merging two sorted lists uses linear extra memory. The addi-
tional work involved in copying to the temporary array and back, throughout
the algorithm, slows the sort considerably. This copying can be avoided by
judiciously switching the roles of a and tmpArray at alternate levels in the
recursion. A variant of mergesort can also be implemented nonrecursively.
The running time of mergesort depends heavily on the relative costs of
comparing elements and moving elements in the array (and the temporary
array). In the case of sorting general objects in Java, an element comparison is
expensive because in a general setting, the comparison is done by function
objects. On the other hand, moving elements is inexpensive because the ele-
ments are not copied; instead, references simply change. Mergesort uses the
fewest number of comparisons of all the popular sorting algorithms and thus
is a good candidate for general-purpose sorting in Java. In fact, it is the algo-
rithm used in java.util.Arrays.sort to sort arrays of objects. These relative
costs do not apply in other languages, nor do they apply for sorting primitive

Excessive copying
can be avoided
with more work, but
the linear extra
memory cannot be
removed without
excessive time
penalties.