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

The performance of Shellsort is quite acceptable in practice, even for N in
the tens of thousands. The simplicity of the code makes it the algorithm of
choice for sorting up to moderately large input. It is also a fine example of a
very simple algorithm with an extremely complex analysis.

Shellsort is a good
choice for moder-
ate amounts of
input.

mergesort

8.5

Recall from Section 7.5 that recursion can be used to develop subquadratic
algorithms. Specifically, a divide-and-conquer algorithm in which two half-
size problems are solved recursively with an O ( N ) overhead results in the
algorithm O ( N log N ). Mergesort is such an algorithm. It offers a better
bound, at least theoretically, than the bounds claimed for Shellsort.
The mergesort algorithm involves three steps.

Mergesort uses
divide-and-con-
quer to obtain an
O ( N log N ) run-
ning time.

1. If the number of items to sort is 0 or 1, return.

2. Recursively sort the first and second halves separately.

3. Merge the two sorted halves into a sorted group.

To claim an O ( N log N ) algorithm, we need only to show that the merging of
two sorted groups can be performed in linear time. In this section we show how to
merge two input arrays, A and B, placing the result in a third array, C . We then
provide a simple implementation of mergesort. The merge routine is the corner-
stone of most external sorting algorithms, as demonstrated in Section 21.6.

Merging of sorted
arrays can be done
in linear time.

8.5.1 linear-time merging of sorted arrays

The basic merge algorithm takes two input arrays, A and B, an output array, C,
and three counters, Actr, Bctr, and Cctr, which are initially set to the beginning
of their respective arrays. The smaller of A[Actr] and B[Bctr] is copied to the
next entry in C, and the appropriate counters are advanced. When either input
array is exhausted, the rest of the other array is copied to C .
An example of how the merge routine works is provided for the following
input:

1 13 24 26 2 15 27 38

Actr Bctr

Cctr