Given two sorted subsequences [ first...middle ) and [ middle...last ) within the range [ first...last ), merge the two subsequences into one sorted sequence from [ first...last ). This merge is stable in that if both ranges contain equal values, the value from the first range will be stored first. The first version assumes that the ranges [ first...middle ) and [ middle...last ) are sorted using operator< .

Declaration


  
#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 compare
  );

Complexity

Given enough memory, this algorithm's time complexity is linear and its space complexity is ( last - first ). If enough memory is not available, the time complexity becomes N * log(N) and the space complexity becomes constant.

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


    #include <iostream>
#include <algorithm>

int numbers[ 6 ] = { 1, 10, 42, 3, 16, 32 };

void
main()
  {
  int i = 0;
  for ( ; i < 6; ++i )
    cout << numbers[ i ] << ` `;
  cout << "\n";

  inplace_merge( numbers, numbers + 3, numbers + 6 );

  for ( i = 0; i < 6; ++i )
    cout << numbers[ i ] << ` `;
  cout << "\n";
  }

1 10 42 3 16 32
1 3 10 16 32 42

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


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

void
main()
  {
  vector< int > v1( 10 );
  for ( size_t i = 0; i < v1.size(); ++i )
    v1[ i ] =( v1.size() - i - 1 ) % 5;
  ostream_iterator< int > iter( cout, " " );
  copy( v1.begin(), v1.end(), iter );
  cout << "\n";

  inplace_merge
    (
    v1.begin(),
    v1.begin() + 5,
    v1.end(),
    greater< int >()
    );

  copy( v1.begin(), v1.end(), iter );
  cout << "\n";
  }

4 3 2 1 0 4 3 2 1 0
4 4 3 3 2 2 1 1 0 0

inplace_merge

Library

Declaration

Complexity

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

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