template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2,
WeaklyIncrementable O, class Comp = less<>, class Proj1 = identity,
class Proj2 = identity>
requires Mergeable<I1, I2, O, Comp, Proj1, Proj2>
tagged_tuple<tag::in1(I1), tag::in2(I2), tag::out(O)>
merge(I1 first1, S1 last1, I2 first2, S2 last2, O result,
Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
template <InputRange Rng1, InputRange Rng2, WeaklyIncrementable O, class Comp = less<>,
class Proj1 = identity, class Proj2 = identity>
requires Mergeable<iterator_t<Rng1>, iterator_t<Rng2>, O, Comp, Proj1, Proj2>
tagged_tuple<tag::in1(safe_iterator_t<Rng1>),
tag::in2(safe_iterator_t<Rng2>),
tag::out(O)>
merge(Rng1&& rng1, Rng2&& rng2, O result,
Comp comp = Comp{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{});
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). 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.
Requires: The ranges [first1,last1) and [first2,last2) shall be sorted with respect to comp, proj1, and proj2. The resulting range shall not overlap with either of the original ranges.
Returns: make_tagged_tuple<tag::in1, tag::in2, tag::out>(last1, last2, result_last).
Complexity: At most (last1 - first1) + (last2 - first2) - 1 applications of the comparison function and each projection.
Remarks: Stable ( ISO/IEC 14882:2014 §[algorithm.stable]).
template <BidirectionalIterator I, Sentinel<I> S, class Comp = less<>,
class Proj = identity>
requires Sortable<I, Comp, Proj>
I
inplace_merge(I first, I middle, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <BidirectionalRange Rng, class Comp = less<>, class Proj = identity>
requires Sortable<iterator_t<Rng>, Comp, Proj>
safe_iterator_t<Rng>
inplace_merge(Rng&& rng, iterator_t<Rng> middle, Comp comp = Comp{},
Proj proj = Proj{});
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 invoke(comp, invoke(proj, *i), invoke(proj, *(i - 1))) will be false.
Requires: The ranges [first,middle) and [middle,last) shall be sorted with respect to comp and proj.
Returns: last
Complexity: When enough additional memory is available, (last - first) - 1 applications of the comparison function and projection. 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 ( ISO/IEC 14882:2014 §[algorithm.stable]).