# 28 Algorithms library [algorithms]

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

### 28.7.5 Merge [alg.merge]

```template<class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator> ForwardIterator merge(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result); template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare> OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class ForwardIterator, class Compare> ForwardIterator merge(ExecutionPolicy&& exec, ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, ForwardIterator result, Compare comp); ```

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.

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.

Returns: result + (last1 - first1) + (last2 - first2).

Complexity: Let N=(last1 - first1) + (last2 - first2):

• For the overloads with no ExecutionPolicy, at most N1 comparisons.

• For the overloads with an ExecutionPolicy, O(N) comparisons.

Remarks: Stable.

```template<class BidirectionalIterator> void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last); template<class ExecutionPolicy, class BidirectionalIterator> void inplace_merge(ExecutionPolicy&& exec, BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last); template<class BidirectionalIterator, class Compare> void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp); template<class ExecutionPolicy, class BidirectionalIterator, class Compare> void inplace_merge(ExecutionPolicy&& exec, BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp); ```

Requires: The ranges [first, middle) and [middle, last) shall be sorted with respect to operator< or comp. BidirectionalIterator shall satisfy the requirements of ValueSwappable. The type of *first shall satisfy the requirements of MoveConstructible and of MoveAssignable.

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.

Complexity: Let N=last - first:

• For the overloads with no ExecutionPolicy, if enough additional memory is available, exactly N1 comparisons.

• For the overloads with no ExecutionPolicy if no additional memory is available, O(NlogN) comparisons.

• For the overloads with an ExecutionPolicy, O(NlogN) comparisons.

Remarks: Stable.