25 Algorithms library [algorithms]

25.8 Sorting and related operations [alg.sorting]

25.8.5 Merge [alg.merge]

template<class InputIterator1, class InputIterator2, class OutputIterator> constexpr 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> constexpr 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); template<input_­iterator I1, sentinel_­for<I1> S1, input_­iterator I2, sentinel_­for<I2> S2, weakly_­incrementable O, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires mergeable<I1, I2, O, Comp, Proj1, Proj2> constexpr ranges::merge_result<I1, I2, O> ranges::merge(I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); template<input_­range R1, input_­range R2, weakly_­incrementable O, class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity> requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2> constexpr ranges::merge_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O> ranges::merge(R1&& r1, R2&& r2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
Let N be (last1 - first1) + (last2 - first2).
Let comp be less{}, proj1 be identity{}, and proj2 be identity{}, for the overloads with no parameters by those names.
Preconditions: The ranges [first1, last1) and [first2, last2) are sorted with respect to comp and proj1 or proj2, respectively.
The resulting range does 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 + N.
If an element a precedes b in an input range, a is copied into the output range before b.
If e1 is an element of [first1, last1) and e2 of [first2, last2), e2 is copied into the output range before e1 if and only if bool(invoke(comp, invoke(proj2, e2), invoke(proj1, e1))) is true.
Returns:
  • result_­last for the overloads in namespace std.
  • {last1, last2, result_­last} for the overloads in namespace ranges.
Complexity:
  • For the overloads with no ExecutionPolicy, at most comparisons and applications of each projection.
  • For the overloads with an ExecutionPolicy, comparisons.
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); template<bidirectional_­iterator I, sentinel_­for<I> S, class Comp = ranges::less, class Proj = identity> requires sortable<I, Comp, Proj> I ranges::inplace_merge(I first, I middle, S last, Comp comp = {}, Proj proj = {});
Let comp be less{} and proj be identity{} for the overloads with no parameters by those names.
Preconditions: [first, middle) and [middle, last) are valid ranges sorted with respect to comp and proj.
For the overloads in namespace std, BidirectionalIterator meets the Cpp17ValueSwappable requirements ([swappable.requirements]) and the type of *first meets the Cpp17MoveConstructible (Table 28) and Cpp17MoveAssignable (Table 30) requirements.
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 is sorted with respect to comp and proj.
Returns: last for the overload in namespace ranges.
Complexity: Let :
  • For the overloads with no ExecutionPolicy, and if enough additional memory is available, exactly comparisons.
  • Otherwise, comparisons.
In either case, twice as many projections as comparisons.
Remarks: Stable.
template<bidirectional_­range R, class Comp = ranges::less, class Proj = identity> requires sortable<iterator_t<R>, Comp, Proj> borrowed_iterator_t<R> ranges::inplace_merge(R&& r, iterator_t<R> middle, Comp comp = {}, Proj proj = {});
Effects: Equivalent to:
return ranges::inplace_merge(ranges::begin(r), middle, ranges::end(r), comp, proj);