std::inplace_merge

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

default (1)

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

custom (2)

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 elements are compared using operator< for the first version, and comp for the second. The elements in both ranges shall already be ordered according to this same criterion (operator< or comp). The resulting range is also sorted according to this.

The function preserves the relative order of elements with equivalent values, with the elements in the first range preceding those equivalent in the second.

Parameters

first: Bidirectional iterator to the initial position in the first sorted sequence to merge. This is also the initial position where the resulting merged range is stored.
middle: Bidirectional iterator to the initial position of the second sorted sequence, which because both sequences must be consecutive, matches the past-the-end position of the first sequence.
last: Bidirectional iterator to the past-the-end position of the second sorted sequence. This is also the past-the-end position of the range where the resulting merged range is stored.
comp: Binary function that accepts two arguments of the types pointed by the iterators, and returns a value convertible to bool. The value returned indicates whether the first argument is considered to go before the second in the specific strict weak ordering it defines.
The function shall not modify any of its arguments.
This can either be a function pointer or a function object.

BidirectionalIterator shall point to a type for which swap is properly defined and which is both move-constructible and move-assignable.

Return value

none

Example

// inplace_merge example
#include <iostream>     // std::cout
#include <algorithm>    // std::inplace_merge, std::sort, std::copy
#include <vector>       // std::vector

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

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

  it=std::copy (first, first+5, v.begin());
     std::copy (second,second+5,it);

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

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

  return 0;
}

Output:

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

Complexity

If enough extra memory is available, linear in the distance between first and last: Performs N-1 comparisons and up to twice that many element moves.
Otherwise, up to linearithmic: Performs up to N*log(N) element comparisons (where N is the distance above), and up to that many element swaps.

Data races

The objects in the range [first,last) are modified.

Exceptions

Throws if any of the element comparisons, the element swaps (or moves) or the operations on iterators throws.
Note that invalid arguments cause undefined behavior.