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);
1
#
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.
2
#
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.
3
#
Returns: result + (last1 - first1) + (last2 - first2).
4
#
Complexity: Let :
  • (4.1)
    For the overloads with no ExecutionPolicy, at most comparisons.
  • (4.2)
    For the overloads with an ExecutionPolicy, comparisons.
5
#
Remarks: Stable ([algorithm.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);
6
#
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 23) and of MoveAssignable (Table 25).
7
#
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.
8
#
Complexity: Let :
  • (8.1)
    For the overloads with no ExecutionPolicy, if enough additional memory is available, exactly comparisons.
  • (8.2)
    For the overloads with no ExecutionPolicy if no additional memory is available, comparisons.
  • (8.3)
    For the overloads with an ExecutionPolicy, comparisons.
9
#
Remarks: Stable ([algorithm.stable]).