Standard C++	Library
 		 Copyright 1996, Rogue Wave Software, Inc.

 NAME

   merge	 - Merge two sorted sequences into a third sequence.

 SYNOPSIS

   #include <algorithm>

   template <class InputIterator1, class	InputIterator2,
 	   class OutputIterator>
    OutputIterator
     merge(InputIterator	first1,	InputIterator1 last1,
 	 InputIterator2	first2,	InputIterator last2,
 	 OutputIterator	result);

   template <class InputIterator1, class	InputIterator2,
 	   class OutputIterator, class Compare>
    OutputIterator
     merge(InputIterator1 first1, InputIterator1	last1,
 	 InputIterator2	first2,	InputIterator last2,
 	 OutputIterator	result,	Compare	comp);

 DESCRIPTION

   The merge algorithm merges two sorted	sequences, specified by
   [first1, last1) and [first2, last2), into the sequence
   specified by [result, result + (last1 - first1) + (last2 -
   first2)).  The first version of	the merge algorithm uses the
   less than operator	(<) to compare elements	in the two sequences.
   The second version uses the comparison function provided by the
   function call.  If a comparison function is provided,	merge assumes
   that both sequences were sorted using that	comparison function.

   The merge is stable. This means that if the two original sequences
   contain equivalent elements, the elements from the first sequence
   will always	precede the matching elements from the second in
   the resulting sequence.	 The size of the result of	a
   merge	is equal to the	sum of the sizes of the	two argument
   sequences.  merge returns an	iterator that points to	the end	of the
   resulting	sequence, i.e.,	result + (last1	- first1) + (last2
   -first2). The result of	merge is undefined if the resulting
   range overlaps with either of the	original ranges.

   merge	assumes	that there are at least	(last1 - first1) + (last2 -
   first2) elements following result, unless result has been adapted by
   an insert iterator.

 COMPLEXITY

   For merge at most (last - first1) + (last2 - first2) - 1 comparisons
   are performed.

 EXAMPLE

   //
   // merge.cpp
   //
    #include <algorithm>
    #include <vector>
    #include <iostream.h>

   int main()
    {
     int	d1[4] =	{1,2,3,4};
     int	d2[8] =	{11,13,15,17,12,14,16,18};

      //	Set up two vectors
     vector<int>	v1(d1,d1 + 4), v2(d1,d1	+ 4);
      //	Set up four destination	vectors
     vector<int>	v3(d2,d2 + 8),v4(d2,d2 + 8),
 		v5(d2,d2 + 8),v6(d2,d2 + 8);
      //	Set up one empty vector
     vector<int>	v7;

      //	Merge v1 with v2
      merge(v1.begin(),v1.end(),v2.begin(),v2.end(),v3.begin());
      //	Now use	comparator
      merge(v1.begin(),v1.end(),v2.begin(),v2.end(),v4.begin(),
 	  less<int>());

      //	In place merge v5
     vector<int>::iterator mid =	v5.begin();
     advance(mid,4);
     inplace_merge(v5.begin(),mid,v5.end());
      //	Now use	a comparator on	v6
     mid	= v6.begin();
     advance(mid,4);
     inplace_merge(v6.begin(),mid,v6.end(),less<int>());

      //	Merge v1 and v2	to empty vector	using insert iterator
      merge(v1.begin(),v1.end(),v2.begin(),v2.end(),
 	  back_inserter(v7));

      //	Copy all cout
     ostream_iterator<int,char> out(cout," ");
     copy(v1.begin(),v1.end(),out);
     cout << endl;
     copy(v2.begin(),v2.end(),out);
     cout << endl;
     copy(v3.begin(),v3.end(),out);
     cout << endl;
     copy(v4.begin(),v4.end(),out);
     cout << endl;
     copy(v5.begin(),v5.end(),out);
     cout << endl;
     copy(v6.begin(),v6.end(),out);
     cout << endl;
     copy(v7.begin(),v7.end(),out);
     cout << endl;

      //	Merge v1 and v2	to cout
      merge(v1.begin(),v1.end(),v2.begin(),v2.end(),
 	  ostream_iterator<int,char>(cout," "));
     cout << endl;

     return 0;
    }

   Output :
   1 2 3	4
   1 2 3	4
   1 1 2	2 3 3 4	4
   1 1 2	2 3 3 4	4
   11 12	13 14 15 16 17 18
   11 12	13 14 15 16 17 18
   1 1 2	2 3 3 4	4
   1 1 2	2 3 3 4	4

 WARNING

   If your compiler does	not support default template parameters	then
   you need to always supply the Allocator template argument.  For
   instance you'll have to write:

   vector<int,allocator<int> >

   instead of:

   vector<int>

 SEE ALSO

   Containers, inplace_merge

 STANDARDS CONFORMANCE
   ANSI X3J16/ISO WG21 Joint C++	Committee