# 11 Algorithms library [algorithms]

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

### 11.5.4 Merge [alg.merge]

``` 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]).