merge


Category: algorithms 
Component type: function 
Prototype
Merge is an overloaded name: there are actually two merge functions.
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
template <class InputIterator1, class InputIterator2, class OutputIterator,
class StrictWeakOrdering>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, StrictWeakOrdering comp);
Description
Merge combines two sorted ranges [first1, last1) and
[first2, last2) into a single sorted range. That is, it copies
elements from [first1, last1) and [first2, last2) into
[result, result + (last1  first1) + (last2  first2)) such that
the resulting range is in ascending order.
Merge is stable, meaning both that
the relative order of elements within each input range is preserved,
and that for equivalent [1] elements in both input ranges the element
from the first range precedes the element from the second.
The return value is result + (last1  first1) + (last2  first2).
The two versions of merge differ in how elements are compared.
The first version uses operator<. That is, the input ranges and
the output range satisfy the condition that for every pair of
iterators i and j such that i precedes j, *j < *i is false.
The second version uses the function object comp.
That is, the input ranges and the output range satisfy the condition
that for every pair of
iterators i and j such that i precedes j, comp(*j, *i) is false.
Definition
Defined in the standard header algorithm, and in the nonstandard
backwardcompatibility header algo.h.
Requirements on types
For the first version:

InputIterator1 is a model of Input Iterator.

InputIterator2 is a model of Input Iterator.

InputIterator1's value type is the same type as InputIterator2's
value type.

InputIterator1's value type is a model of LessThan Comparable.

The ordering on objects of InputIterator1's value type is a
strict weak ordering, as defined in the LessThan Comparable
requirements.

InputIterator1's value type is convertible to a type in OutputIterator's
set of value types.
For the second version:

InputIterator1 is a model of Input Iterator.

InputIterator2 is a model of Input Iterator.

InputIterator1's value type is the same type as InputIterator2's
value type.

StrictWeakOrdering is a model of Strict Weak Ordering.

InputIterator1's value type is convertible to StrictWeakOrdering's
argument type.

InputIterator1's value type is convertible to a type in OutputIterator's
set of value types.
Preconditions
For the first version:

[first1, last1) is a valid range.

[first1, last1) is in ascending order. That is, for every pair
of iterators i and j in [first1, last1) such that i precedes
j, *j < *i is false.

[first2, last2) is a valid range.

[first2, last2) is in ascending order. That is, for every pair
of iterators i and j in [first2, last2) such that i precedes
j, *j < *i is false.

The ranges [first1, last1) and
[result, result + (last1  first1) + (last2  first2)) do not overlap.

The ranges [first2, last2) and
[result, result + (last1  first1) + (last2  first2)) do not overlap.

There is enough space to hold all of the elements being copied.
More formally, the requirement is that
[result, result + (last1  first1) + (last2  first2)) is a valid range.
For the second version:

[first1, last1) is a valid range.

[first1, last1) is in ascending order. That is, for every pair
of iterators i and j in [first1, last1) such that i precedes
j, comp(*j, *i) is false.

[first2, last2) is a valid range.

[first2, last2) is in ascending order. That is, for every pair
of iterators i and j in [first2, last2) such that i precedes
j, comp(*j, *i) is false.

The ranges [first1, last1) and
[result, result + (last1  first1) + (last2  first2)) do not overlap.

The ranges [first2, last2) and
[result, result + (last1  first1) + (last2  first2)) do not overlap.

There is enough space to hold all of the elements being copied.
More formally, the requirement is that
[result, result + (last1  first1) + (last2  first2)) is a valid range.
Complexity
Linear. No comparisons if both [first1, last1) and [first2, last2)
are empty ranges, otherwise at most (last1  first1) + (last2 
first2)  1 comparisons.
Example
int main()
{
int A1[] = { 1, 3, 5, 7 };
int A2[] = { 2, 4, 6, 8 };
const int N1 = sizeof(A1) / sizeof(int);
const int N2 = sizeof(A2) / sizeof(int);
merge(A1, A1 + N1, A2, A2 + N2,
ostream_iterator<int>(cout, " "));
// The output is "1 2 3 4 5 6 7 8"
}
Notes
[1]
Note that you may use an ordering that is a strict weak ordering
but not a total ordering; that is, there might be values x and y
such that x < y, x > y, and x == y are all false. (See the
LessThan Comparable requirements for a more complete discussion.)
Two elements x and y are equivalent if neither x < y nor
y < x. If you're using a total ordering, however (if you're
using strcmp, for example, or if you're using ordinary arithmetic
comparison on integers), then you can ignore this technical
distinction: for a total ordering, equality and equivalence are
the same.
See also
inplace_merge, set_union, sort
STL Main Page