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: Диапазоны [first1, last1) и [first2, last2) должны быть отсортированы относительно operator< или comp. Результирующий диапазон не должен перекрываться ни с одним из исходных диапазонов.

Effects: Копирует все элементы двух диапазонов [first1, last1) и [first2, last2) в диапазон [result, result_last), где result_last есть result + (last1 - first1) + (last2 - first2), так что результирующий диапазон удовлетворяет is_sorted(result, result_last) или is_sorted(result, result_last, comp), соответственно.

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

Complexity: Пусть $N = (last1 - first1) + (last2 - first2)$ :

(4.1)
Для перегрузок без сравнений, ExecutionPolicyмаксимум $N - 1$ .
(4.2)
Для перегрузок ExecutionPolicy, $O (N)$ сравнений.

Remarks: 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: Диапазоны [first, middle) и [middle, last) должны быть отсортированы относительно operator< или comp. BidirectionalIterator должны удовлетворять требованиям ValueSwappable. Тип *first должен удовлетворять требованиям MoveConstructible и MoveAssignable.

Effects: Объединяет два отсортированных последовательных диапазона [first, middle) и [middle, last), помещая результат слияния в диапазон [first, last). Результирующий диапазон будет в порядке неубывания; то есть, для каждого итератора i в [first, last) другом чем first, состояние *i < *(i - 1) или, соответственно, comp(*i, *(i - 1)) будет false.

Complexity: Пусть $N = last - first$ :

(8.1)
Для перегрузок с отсутствием ExecutionPolicy, если доступно достаточно дополнительной памяти, именно $N - 1$ сравнения.
(8.2)
Для перегрузок с нет, ExecutionPolicy если дополнительная память недоступна, $O (N log N)$ сравнения.
(8.3)
Для перегрузок ExecutionPolicy, $O (N log N)$ сравнений.

Remarks: Stable.