.\" ident	@(#)Array_alg:man/merge.3	3.2
.\"
.\" C++ Standard Components, Release 3.0.
.\"
.\" Copyright (c) 1991, 1992 AT&T and UNIX System Laboratories, Inc.
.\" Copyright (c) 1988, 1989, 1990 AT&T.  All Rights Reserved.
.\"
.\" THIS IS UNPUBLISHED PROPRIETARY SOURCE CODE OF AT&T and UNIX System
.\" Laboratories, Inc.  The copyright notice above does not evidence
.\" any actual or intended publication of such source code.
.\" 
.TH \f3merge\fP \f3Array_alg(3C++)\fP " "
.SH NAME
merge \- combine two sorted arrays into one
.SH SYNOPSIS OF Array_alg.h
.Bf

    template <class \*(gt>
    void merge(
	const \*(gt* b1, const \*(gt* e1,
	const \*(gt* b2, const \*(gt* e2,
	\*(gt* b3
    );
    template <class \*(gt>
    void merge_r(
	int (*rel)(const \*(gt*, const \*(gt*),
	const \*(gt* b1, const \*(gt* e1,
	const \*(gt* b2, const \*(gt* e2,
	\*(gt* b3
    );
.Be
.SH ASSUMPTIONS
.PP
(1) For the plain version, \f4\*(gt::operator<\f1
defines a total ordering relation on \*(gt and the array is
sorted w.r.t. that relation.
.br
(2) For the relational version, \f4rel\f1 defines 
a total ordering relation on \*(gt and the array is
sorted w.r.t. that relation.
.br
(3) The output array does not overlap either of the 
two input arrays
.br
(4) The output array has at least as many cells as
both input arrays combined
.br
(5) \*(gt has \f4operator=\f1
.SH DESCRIPTION
.PP
These functions stably combine the elements of
two sorted arrays into a new sorted array.
.sp 0.5v
.IP "\f4template <class \*(gt>\f1"
.IC "\f4void merge(\f1"
.IC "\f4    const \*(gt* b1, const \*(gt* e1,\f1"
.IC "\f4    const \*(gt* b2, const \*(gt* e2,\f1"
.IC "\f4    \*(gt* b3\f1"
.IC "\f4);\f1"
Uses \f4\*(gt::operator<\f1 to define the ordering relation. 
.IP "\f4template <class \*(gt>\f1"
.IC "\f4void merge_r(\f1"
.IC "\f4    int (*rel)(const \*(gt*, const \*(gt*),\f1"
.IC "\f4    const \*(gt* b1, const \*(gt* e1,\f1"
.IC "\f4    const \*(gt* b2, const \*(gt* e2,\f1"
.IC "\f4    \*(gt* b3\f1"
.IC "\f4);\f1"
Uses \f4rel\f1 to define the ordering relation.
.SH COMPLEXITY
.PP
If \f2N\f1 and \f2M\f1 are the sizes of the two arrays, then
complexity is \f2O(N+M)\f1.
At most \f2N+M\-1\f1 tests of the ordering relation and
\f2N+M\f1 assignments are done.
.SH NOTES
Because a Block (see \f3Block(3C++)\f1)
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.
.SH SEE ALSO
.Bf
\f3intro(.)\f1
\f3Block(3C++)\f1
.Be