The fourth class of sorting algorithm we consider comprises
algorithms that sort *by merging* .
Merging is the combination of two or more sorted sequences
into a single sorted sequence.

Figure illustrates the basic, two-way merge operation.
In a two-way merge, two sorted sequences are merged into one.
Clearly, two sorted sequences each of length *n*
can be merged into a sorted sequence of length 2*n*
in *O*(2*n*)=*O*(*n*) steps.
However in order to do this,
we need space in which to store the result.
I.e., it is not possible to merge the two sequences *in place*
in *O*(*n*) steps.

Sorting by merging is a recursive, divide-and-conquer strategy.
In the base case, we have a sequence with exactly one element in it.
Since such a sequence is already sorted, there is nothing to be done.
To sort a sequence of *n**>*1 elements:

- Divide the sequence into two sequences of length and ;
- recursively sort each of the two subsequences; and then,
- merge the sorted subsequences to obtain the final result.

Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.