inplace_merge


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

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

none

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
// 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

Linear in comparisons (N-1) if an internal buffer was used, NlogN otherwise (where N is the number elements in the range [first,last)).

See also

merge Merge sorted ranges (function template)
partition Partition range in two (function template)
includes Test whether sorted range includes another sorted range (function template)