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 :
  • For the overloads with no ExecutionPolicy, at most comparisons.
  • For the overloads with an ExecutionPolicy, 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 :
  • For the overloads with no ExecutionPolicy, if enough additional memory is available, exactly comparisons.
  • For the overloads with no ExecutionPolicy if no additional memory is available, comparisons.
  • For the overloads with an ExecutionPolicy, comparisons.
Remarks: Stable.