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 comp);
Effects: Copies all the elements of the two ranges [first1,last1) and [first2,last2) into the range [result,result_last), where result_last is result + (last1 - first1) + (last2 - first2), such that the resulting range satisfies is_sorted(result, result_last) or is_sorted(result, result_last, comp), respectively.
Requires: The ranges [first1,last1) and [first2,last2) shall be sorted with respect to operator< or comp. The resulting range shall not overlap with either of the original ranges.
Returns: result + (last1 - first1) + (last2 - first2).
Complexity: At most (last1 - first1) + (last2 - first2) - 1 comparisons.
Remarks: Stable.
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);
Effects: Merges two sorted consecutive ranges [first,middle) and [middle,last), putting the result of the merge into the range [first,last). The resulting range will be in non-decreasing order; that is, for every iterator i in [first,last) other than first, the condition *i < *(i - 1) or, respectively, comp(*i, *(i - 1)) will be false.
Requires: The ranges [first,middle) and [middle,last) shall be sorted with respect to operator< or comp. BidirectionalIterator shall satisfy the requirements of ValueSwappable ([swappable.requirements]). The type of *first shall satisfy the requirements of MoveConstructible (Table [moveconstructible]) and of MoveAssignable (Table [moveassignable]).
Complexity: When enough additional memory is available, (last - first) - 1 comparisons. If no additional memory is available, an algorithm with complexity N log(N) (where N is equal to last - first) may be used.
Remarks: Stable.