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

 NAME

   inplace_merge	 - Merge two sorted sequences into one.

 SYNOPSIS

   #include <algorithm>
   template <class BidirectionalIterator>
    void	inplace_merge(BidirectionalIterator first,
 		      BidirectionalIterator middle,
 		      BidirectionalIterator last);

   template <class BidirectionalIterator, class Compare>
    void	inplace_merge(BidirectionalIterator first,
 		      BidirectionalIterator middle,
 		      BidirectionalIterator last, Compare comp);

 DESCRIPTION

   The inplace_merge algorithm merges two sorted	consecutive ranges
   [first, middle) and [middle, last), and puts the result of the merge
   into the	range [first, last).  The merge is stable, that is,
   if the two ranges contain equivalent elements, the elements from the
   first range always	precede	the elements from	the second.

   There	are two	versions of the	inplace_merge algorithm.  The first
   version uses the less	than operator (operator<) as the default for
   comparison, and the second version accepts a third argument that
   specifies a comparison operator.

 COMPLEXITY

   When enough additional memory	is available, inplace_merge does at
   most (last	- first) - 1  comparisons. If no additional memory is
   available, an algorithm with O(NlogN) complexity (where N is equal
   to last-first) may be used.

 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

 WARNINGS

   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

   merge

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