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

<algorithm>

Merge consecutive sorted ranges

Merges two consecutive sorted ranges: [first,middle) and [middle,last), putting the result into the combined sorted range [first,last). The comparison for sorting uses either operator< for the first version, or comp for the second.

For the function to yield the expected result, the elements of each of both ranges shall already be ordered (independently for each range) according to the same strict weak ordering criterion used by this function (operator< or comp). The resulting range is also sorted according to it.

Parameters

first

Bidirectional iterator to the initial position in the first sequence to be merged. This is also the initial position of where the resulting merged range is stored.

middle

Bidirectional iterator to the initial position of the second sequence, which because both sequences must be consecutive, matches the past-the-end position of the first sequence.

last

Bidirectional iterator to the final position of the second sequence. This is also the final position in the resulting merged range is stored.

Return value

Example

// inplace_merge example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main () {
  int first[] = {5,10,15,20,25};
  int second[] = {50,40,30,20,10};
  vector<int> v(10);
  vector<int>::iterator it;

  sort (first,first+5);
  sort (second,second+5);

  copy (first,first+5,v.begin());
  copy (second,second+5,v.begin()+5);

  inplace_merge (v.begin(),v.begin()+5,v.end());

  cout << "The resulting vector contains:";
  for (it=v.begin(); it!=v.end(); ++it)
    cout << " " << *it;

  cout << endl;
  
  return 0;
}

Output:

The resulting vector contains: 5 10 10 15 20 20 25 30 40 50

Complexity

See also