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);

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.

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.

Returns: result + (last1 - first1) + (last2 - first2).

Complexity: Let :

(4.1)
For the overloads with no ExecutionPolicy, at most comparisons.
(4.2)
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);

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

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.

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.

Remarks: Stable ([algorithm.stable]).