27 Algorithms library [algorithms]

27.8 Sorting and related operations [alg.sorting]

27.8.6 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:

(4.1)
result_last for the overloads in namespace std.
(4.2)
{last1, last2, result_last} for the overloads in namespace ranges.

Complexity:

(5.1)
For the overloads with no ExecutionPolicy, at most $N - 1$ comparisons and applications of each projection.
(5.2)
For the overloads with an ExecutionPolicy, $O (N)$ comparisons.

Remarks: Stable ([algorithm.stable]).

🔗

template<class BidirectionalIterator>
  constexpr 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>
  constexpr 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>
  constexpr 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 31) and Cpp17MoveAssignable (Table 33) 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

N = last - first

(11.1)
For the overloads with no ExecutionPolicy, and if enough additional memory is available, exactly $N - 1$ comparisons.
(11.2)
Otherwise, $O (N log N)$ comparisons.

In either case, twice as many projections as comparisons.

Remarks: Stable ([algorithm.stable]).

🔗

template<bidirectional_range R, class Comp = ranges::less, class Proj = identity>
  requires sortable<iterator_t<R>, Comp, Proj>
  constexpr 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);