# merge(3C++)

**merge --
combine two sorted arrays into one
**

## Synopsis

template <class **T**>
void merge(
const **T*** b1, const **T*** e1,
const **T*** b2, const **T*** e2,
**T*** b3
);
template <class **T**>
void merge_r(
int (*rel)(const **T***, const **T***),
const **T*** b1, const **T*** e1,
const **T*** b2, const **T*** e2,
**T*** b3
);

## Assumptions

(1) For the plain version, **T::operator<**
defines a total ordering relation on **T** and the array is sorted
w.r.t. that relation.

(2) For the relational version, **rel** defines a total ordering
relation on **T** and the array is sorted w.r.t. that relation.

(3) The output array does not overlap either of the two input arrays.

(4) The output array has at least as many cells as both input arrays combined.

(5) **T** has **operator=**.

## Description

These functions stably combine the elements of two sorted arrays into a new
sorted array.

template <class T>
void merge(
const T* b1, const T* e1,
const T* b2, const T* e2,
T* b3
);

Uses **T::operator<** to define the ordering relation.

template <class T>
void merge_r(
int (*rel)(const T*, const T*),
const T* b1, const T* e1,
const T* b2, const T* e2,
T* b3
);

Uses **rel** to define the ordering relation.

## Complexity

If *N* and *M* are the sizes
of the two arrays, then complexity is *O(N+M)*. At most
*N+M-1* tests of the ordering relation and
*N+M* assignments are done.

## Notes

Because a Block (see **Block(3C++)**) can always be used wherever
an array is called for, Array Algorithms can also be used with Blocks.
In fact,
these two components were actually designed to be used together.

## References

**Array_alg**(3C++),
**Block**(3C++)

*
© 2004 The SCO Group, Inc. All rights reserved.
*

UnixWare 7 Release 7.1.4 - 25 April 2004