.\" ident	@(#)Array_alg:man/merge_sort.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_sort\fP \f3Array_alg(3C++)\fP " "
.SH NAME
merge_sort \- stably sort an array
.SH SYNOPSIS OF Array_alg.h
.Bf

    template <class \*(gt>
    \*(gt* merge_sort(\*(gt* b1,\*(gt* e1,\*(gt* b2);
    template <class \*(gt>
    \*(gt* merge_sort_r(int (*rel)(const \*(gt*,const \*(gt*),
		        \*(gt* b1,\*(gt* e1,\*(gt* b2);

.Be
.SH ASSUMPTIONS
.PP
(1) For the plain version, \*(gt\f4::operator<\f1
defines a total ordering relation on \*(gt
.br
(2) For the relational version, \f4rel\f1 defines
a total ordering relation on \*(gt.
.br
(3) The two arrays do not overlap
.br
(4) The second array has at least as many cells as
the first array
.br
(5) \*(gt has \f4operator=\f1
.SH DESCRIPTION
.PP
These functions stably sort an array using a merge
sorting algorithm.
The algorithm requires an auxiliary array of the 
same size, identified by the argument \f4b2\f1.
They return a pointer to 
either (1) the original array or
(2) the auxiliary array, depending on which 
one contains the final result of the sort.
.sp 0.5v
.IP "\f4template <class \*(gt>\f1"
.IC "\f4\*(gt* merge_sort(\*(gt* b1,\*(gt* e1,\*(gt* b2);\f1"
Uses \f4\*(gt::operator<\f1 
to define the ordering relation used by the
sorting algorithm.
.IP "\f4template <class \*(gt>\f1"
.IC "\f4\*(gt* merge_sort_r(int (*rel)(const \*(gt*,const \*(gt*),\*(gt* b1,\*(gt* e1,\*(gt* b2);\f1"
Uses \f4rel\f1 
to define the ordering relation used by the
sorting algorithm.
.SH COMPLEXITY
.PP
If \f2N\f1 is the size of the array, then 
complexity is \f2O(NlgN)\f1.
At most \f2NlgN\f1 tests of the ordering relation 
and \f2NlgN\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
\f3ins_sort(.)\f1
\f3sort(.)\f1
\f3Block(3C++)\f1
.Be