# 25 Algorithms library [algorithms]

## 25.4 Sorting and related operations [alg.sorting]

### 25.4.4 Merge [alg.merge]

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.