Merge two sorted ranges into one sorted range, result . Return an iterator equal to result + n where n = ( last1

first1 ) + ( last2 - first2 ). The merge is stable in that if both ranges contain equivalent values, the value of the first range is stored in result before the values in the second range. The result of merging overlapping ranges is undefined. The first version assumes that both ranges are already sorted using operator< , whereas the second version assumes that both ranges are already sorted using the binary function compare .

Declaration


  
#include <algorithm>

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

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

Complexity

Time complexity is O(N) where N =( last1 - first1 ) + ( last2 -first2 ). Space complexity is constant.

Example <ospace/osstd/examples/merge0.cpp>


    #include <iostream>
#include <algorithm>

int numbers1[ 5 ] = { 1, 6, 13, 25, 101 };
int numbers2[ 5 ] = {-5, 26, 36, 46, 99 };

void
main()
  {
  int result[ 10 ];

  merge
    (
    numbers1,
    numbers1 + 5,
    numbers2,
    numbers2 + 5,
    result
    );

  for ( int i = 0; i < 10; ++i )
    cout << result[ i ] << ` `;
  cout << "\n";
  }

-5 1 6 13 25 26 36 46 99 101

Example <ospace/osstd/examples/merge1.cpp>


    #include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>

void
main()
  {
  vector< int > v1( 5 );
  vector< int > v2( v1.size() );
  for ( size_t i = 0; i < v1.size(); ++i )
    {
    v1[ i ] = i;
    v1[ i ] = i + 3;
    }
  vector< int > result( v1.size() + v2.size() );

  merge( v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin() );

  ostream_iterator< int > iter( cout, " " );
  copy( v1.begin(), v1.end(), iter );
  cout << "\n";
  copy( v2.begin(), v2.end(), iter );
  cout << "\n";
  copy( result.begin(), result.end(), iter );
  cout << "\n";
  }

0 1 2 3 4
3 4 5 6 7
0 1 2 3 3 4 4 5 6 7

Example <ospace/osstd/examples/merge2.cpp>


    #include <iostream>
#include <algorithm>
#include <functional>
#include <iterator>
#include <vector>

void
main()
  {
  vector< int > v1( 5 );
  vector< int > v2( v1.size() );
  for ( size_t i = 0; i < v1.size(); ++i )
    {
    v1[ i ] = 10 - i;
    v2[ i ] =  7 - i;
    }
  vector< int > result( v1.size() + v2.size() );

  merge
    (
    v1.begin(),
    v1.end(),
    v2.begin(),
    v2.end(),
    result.begin(),
    greater< int >()
    );

  ostream_iterator< int > iter( cout, " " );
  copy( v1.begin(), v1.end(), iter );
  cout << "\n";
  copy( v2.begin(), v2.end(), iter );
  cout << "\n";
  copy( result.begin(), result.end(), iter );
  cout << "\n";
  }

10 9 8 7 6
7 6 5 4 3
10 9 8 7 7 6 6 5 4 3

merge

Library

Declaration

Complexity

Example <ospace/osstd/examples/merge0.cpp>

Example <ospace/osstd/examples/merge1.cpp>

Example <ospace/osstd/examples/merge2.cpp>