>* __pieces;
+
+ __num_threads = static_cast<_ThreadIndex>
+ (std::min<_DifferenceType>(__num_threads, __total_length));
+
+# pragma omp parallel num_threads (__num_threads)
+ {
+# pragma omp single
+ {
+ __num_threads = omp_get_num_threads();
+ // Thread __t will have to merge pieces[__iam][0..__k - 1]
+ __pieces = new std::vector<
+ std::pair<_DifferenceType, _DifferenceType> >[__num_threads];
+ for (_ThreadIndex __s = 0; __s < __num_threads; ++__s)
+ __pieces[__s].resize(__k);
+
+ _DifferenceType __num_samples =
+ __gnu_parallel::_Settings::get().merge_oversampling
+ * __num_threads;
+
+ __splitter(__ne_seqs, __ne_seqs + __k, __length, __total_length,
+ __comp, __pieces);
+ } //single
+
+ _ThreadIndex __iam = omp_get_thread_num();
+
+ _DifferenceType __target_position = 0;
+
+ for (_SeqNumber __c = 0; __c < __k; ++__c)
+ __target_position += __pieces[__iam][__c].first;
+
+ seq_type* __chunks = new seq_type[__k];
+
+ for (_SeqNumber __s = 0; __s < __k; ++__s)
+ __chunks[__s] = std::make_pair(__ne_seqs[__s].first
+ + __pieces[__iam][__s].first,
+ __ne_seqs[__s].first
+ + __pieces[__iam][__s].second);
+
+ if(__length > __target_position)
+ __sequential_multiway_merge<__stable, __sentinels>
+ (__chunks, __chunks + __k, __target + __target_position,
+ *(__seqs_begin->second), __length - __target_position, __comp);
+
+ delete[] __chunks;
+ } // parallel
+
+#if _GLIBCXX_ASSERTIONS
+ _GLIBCXX_PARALLEL_ASSERT(
+ __is_sorted(__target, __target + __length, __comp));
+#endif
+
+ __k = 0;
+ // Update ends of sequences.
+ for (_RAIterIterator __raii = __seqs_begin;
+ __raii != __seqs_end; ++__raii)
+ {
+ _DifferenceTp __length = _GLIBCXX_PARALLEL_LENGTH(*__raii);
+ if(__length > 0)
+ (*__raii).first += __pieces[__num_threads - 1][__k++].second;
+ }
+
+ delete[] __pieces;
+ delete[] __ne_seqs;
+
+ return __target + __length;
+ }
+
+ /**
+ * @brief Multiway Merge Frontend.
+ *
+ * Merge the sequences specified by seqs_begin and __seqs_end into
+ * __target. __seqs_begin and __seqs_end must point to a sequence of
+ * pairs. These pairs must contain an iterator to the beginning
+ * of a sequence in their first entry and an iterator the _M_end of
+ * the same sequence in their second entry.
+ *
+ * Ties are broken arbitrarily. See stable_multiway_merge for a variant
+ * that breaks ties by sequence number but is slower.
+ *
+ * The first entries of the pairs (i.e. the begin iterators) will be moved
+ * forward.
+ *
+ * The output sequence has to provide enough space for all elements
+ * that are written to it.
+ *
+ * This function will merge the input sequences:
+ *
+ * - not stable
+ * - parallel, depending on the input size and Settings
+ * - using sampling for splitting
+ * - not using sentinels
+ *
+ * Example:
+ *
+ *
+ * int sequences[10][10];
+ * for (int __i = 0; __i < 10; ++__i)
+ * for (int __j = 0; __i < 10; ++__j)
+ * sequences[__i][__j] = __j;
+ *
+ * int __out[33];
+ * std::vector > seqs;
+ * for (int __i = 0; __i < 10; ++__i)
+ * { seqs.push(std::make_pair(sequences[__i],
+ * sequences[__i] + 10)) }
+ *
+ * multiway_merge(seqs.begin(), seqs.end(), __target, std::less(), 33);
+ *
+ *
+ * @see stable_multiway_merge
+ *
+ * @pre All input sequences must be sorted.
+ * @pre Target must provide enough space to merge out length elements or
+ * the number of elements in all sequences, whichever is smaller.
+ *
+ * @post [__target, return __value) contains merged __elements from the
+ * input sequences.
+ * @post return __value - __target = min(__length, number of elements in all
+ * sequences).
+ *
+ * @tparam _RAIterPairIterator iterator over sequence
+ * of pairs of iterators
+ * @tparam _RAIterOut iterator over target sequence
+ * @tparam _DifferenceTp difference type for the sequence
+ * @tparam _Compare strict weak ordering type to compare elements
+ * in sequences
+ *
+ * @param __seqs_begin __begin of sequence __sequence
+ * @param __seqs_end _M_end of sequence __sequence
+ * @param __target target sequence to merge to.
+ * @param __comp strict weak ordering to use for element comparison.
+ * @param __length Maximum length to merge, possibly larger than the
+ * number of elements available.
+ *
+ * @return _M_end iterator of output sequence
+ */
+ // multiway_merge
+ // public interface
+ template
+ _RAIterOut
+ multiway_merge(_RAIterPairIterator __seqs_begin,
+ _RAIterPairIterator __seqs_end,
+ _RAIterOut __target,
+ _DifferenceTp __length, _Compare __comp,
+ __gnu_parallel::sequential_tag)
+ {
+ typedef _DifferenceTp _DifferenceType;
+ _GLIBCXX_CALL(__seqs_end - __seqs_begin)
+
+ // catch special case: no sequences
+ if (__seqs_begin == __seqs_end)
+ return __target;
+
+ // Execute multiway merge *sequentially*.
+ return __sequential_multiway_merge
+
+ (__seqs_begin, __seqs_end, __target,
+ *(__seqs_begin->second), __length, __comp);
+ }
+
+ // public interface
+ template
+ _RAIterOut
+ multiway_merge(_RAIterPairIterator __seqs_begin,
+ _RAIterPairIterator __seqs_end,
+ _RAIterOut __target,
+ _DifferenceTp __length, _Compare __comp,
+ __gnu_parallel::exact_tag __tag)
+ {
+ typedef _DifferenceTp _DifferenceType;
+ _GLIBCXX_CALL(__seqs_end - __seqs_begin)
+
+ // catch special case: no sequences
+ if (__seqs_begin == __seqs_end)
+ return __target;
+
+ // Execute merge; maybe parallel, depending on the number of merged
+ // elements and the number of sequences and global thresholds in
+ // Settings.
+ if ((__seqs_end - __seqs_begin > 1)
+ && _GLIBCXX_PARALLEL_CONDITION(
+ ((__seqs_end - __seqs_begin) >=
+ __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
+ && ((_SequenceIndex)__length >=
+ __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
+ return parallel_multiway_merge
+
+ (__seqs_begin, __seqs_end, __target,
+ multiway_merge_exact_splitting
+ ::value_type*, _Compare, _DifferenceTp>,
+ static_cast<_DifferenceType>(__length), __comp,
+ __tag.__get_num_threads());
+ else
+ return __sequential_multiway_merge
+
+ (__seqs_begin, __seqs_end, __target,
+ *(__seqs_begin->second), __length, __comp);
+ }
+
+ // public interface
+ template
+ _RAIterOut
+ multiway_merge(_RAIterPairIterator __seqs_begin,
+ _RAIterPairIterator __seqs_end,
+ _RAIterOut __target,
+ _DifferenceTp __length, _Compare __comp,
+ __gnu_parallel::sampling_tag __tag)
+ {
+ typedef _DifferenceTp _DifferenceType;
+ _GLIBCXX_CALL(__seqs_end - __seqs_begin)
+
+ // catch special case: no sequences
+ if (__seqs_begin == __seqs_end)
+ return __target;
+
+ // Execute merge; maybe parallel, depending on the number of merged
+ // elements and the number of sequences and global thresholds in
+ // Settings.
+ if ((__seqs_end - __seqs_begin > 1)
+ && _GLIBCXX_PARALLEL_CONDITION(
+ ((__seqs_end - __seqs_begin) >=
+ __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
+ && ((_SequenceIndex)__length >=
+ __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
+ return parallel_multiway_merge
+
+ (__seqs_begin, __seqs_end, __target,
+ multiway_merge_exact_splitting
+ ::value_type*, _Compare, _DifferenceTp>,
+ static_cast<_DifferenceType>(__length), __comp,
+ __tag.__get_num_threads());
+ else
+ return __sequential_multiway_merge
+
+ (__seqs_begin, __seqs_end, __target,
+ *(__seqs_begin->second), __length, __comp);
+ }
+
+ // public interface
+ template
+ _RAIterOut
+ multiway_merge(_RAIterPairIterator __seqs_begin,
+ _RAIterPairIterator __seqs_end,
+ _RAIterOut __target,
+ _DifferenceTp __length, _Compare __comp,
+ parallel_tag __tag = parallel_tag(0))
+ { return multiway_merge(__seqs_begin, __seqs_end, __target, __length,
+ __comp, exact_tag(__tag.__get_num_threads())); }
+
+ // public interface
+ template
+ _RAIterOut
+ multiway_merge(_RAIterPairIterator __seqs_begin,
+ _RAIterPairIterator __seqs_end,
+ _RAIterOut __target,
+ _DifferenceTp __length, _Compare __comp,
+ default_parallel_tag __tag)
+ { return multiway_merge(__seqs_begin, __seqs_end, __target, __length,
+ __comp, exact_tag(__tag.__get_num_threads())); }
+
+ // stable_multiway_merge
+ // public interface
+ template
+ _RAIterOut
+ stable_multiway_merge(_RAIterPairIterator __seqs_begin,
+ _RAIterPairIterator __seqs_end,
+ _RAIterOut __target,
+ _DifferenceTp __length, _Compare __comp,
+ __gnu_parallel::sequential_tag)
+ {
+ typedef _DifferenceTp _DifferenceType;
+ _GLIBCXX_CALL(__seqs_end - __seqs_begin)
+
+ // catch special case: no sequences
+ if (__seqs_begin == __seqs_end)
+ return __target;
+
+ // Execute multiway merge *sequentially*.
+ return __sequential_multiway_merge
+
+ (__seqs_begin, __seqs_end, __target,
+ *(__seqs_begin->second), __length, __comp);
+ }
+
+ // public interface
+ template
+ _RAIterOut
+ stable_multiway_merge(_RAIterPairIterator __seqs_begin,
+ _RAIterPairIterator __seqs_end,
+ _RAIterOut __target,
+ _DifferenceTp __length, _Compare __comp,
+ __gnu_parallel::exact_tag __tag)
+ {
+ typedef _DifferenceTp _DifferenceType;
+ _GLIBCXX_CALL(__seqs_end - __seqs_begin)
+
+ // catch special case: no sequences
+ if (__seqs_begin == __seqs_end)
+ return __target;
+
+ // Execute merge; maybe parallel, depending on the number of merged
+ // elements and the number of sequences and global thresholds in
+ // Settings.
+ if ((__seqs_end - __seqs_begin > 1)
+ && _GLIBCXX_PARALLEL_CONDITION(
+ ((__seqs_end - __seqs_begin) >=
+ __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
+ && ((_SequenceIndex)__length >=
+ __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
+ return parallel_multiway_merge
+
+ (__seqs_begin, __seqs_end, __target,
+ multiway_merge_exact_splitting
+ ::value_type*, _Compare, _DifferenceTp>,
+ static_cast<_DifferenceType>(__length), __comp,
+ __tag.__get_num_threads());
+ else
+ return __sequential_multiway_merge
+
+ (__seqs_begin, __seqs_end, __target,
+ *(__seqs_begin->second), __length, __comp);
+ }
+
+ // public interface
+ template
+ _RAIterOut
+ stable_multiway_merge(_RAIterPairIterator __seqs_begin,
+ _RAIterPairIterator __seqs_end,
+ _RAIterOut __target,
+ _DifferenceTp __length, _Compare __comp,
+ sampling_tag __tag)
+ {
+ typedef _DifferenceTp _DifferenceType;
+ _GLIBCXX_CALL(__seqs_end - __seqs_begin)
+
+ // catch special case: no sequences
+ if (__seqs_begin == __seqs_end)
+ return __target;
+
+ // Execute merge; maybe parallel, depending on the number of merged
+ // elements and the number of sequences and global thresholds in
+ // Settings.
+ if ((__seqs_end - __seqs_begin > 1)
+ && _GLIBCXX_PARALLEL_CONDITION(
+ ((__seqs_end - __seqs_begin) >=
+ __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
+ && ((_SequenceIndex)__length >=
+ __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
+ return parallel_multiway_merge
+
+ (__seqs_begin, __seqs_end, __target,
+ multiway_merge_sampling_splitting
+ ::value_type*, _Compare, _DifferenceTp>,
+ static_cast<_DifferenceType>(__length), __comp,
+ __tag.__get_num_threads());
+ else
+ return __sequential_multiway_merge
+
+ (__seqs_begin, __seqs_end, __target,
+ *(__seqs_begin->second), __length, __comp);
+ }
+
+ // public interface
+ template
+ _RAIterOut
+ stable_multiway_merge(_RAIterPairIterator __seqs_begin,
+ _RAIterPairIterator __seqs_end,
+ _RAIterOut __target,
+ _DifferenceTp __length, _Compare __comp,
+ parallel_tag __tag = parallel_tag(0))
+ {
+ return stable_multiway_merge
+ (__seqs_begin, __seqs_end, __target, __length, __comp,
+ exact_tag(__tag.__get_num_threads()));
+ }
+
+ // public interface
+ template
+ _RAIterOut
+ stable_multiway_merge(_RAIterPairIterator __seqs_begin,
+ _RAIterPairIterator __seqs_end,
+ _RAIterOut __target,
+ _DifferenceTp __length, _Compare __comp,
+ default_parallel_tag __tag)
+ {
+ return stable_multiway_merge
+ (__seqs_begin, __seqs_end, __target, __length, __comp,
+ exact_tag(__tag.__get_num_threads()));
+ }
+
+ /**
+ * @brief Multiway Merge Frontend.
+ *
+ * Merge the sequences specified by seqs_begin and __seqs_end into
+ * __target. __seqs_begin and __seqs_end must point to a sequence of
+ * pairs. These pairs must contain an iterator to the beginning
+ * of a sequence in their first entry and an iterator the _M_end of
+ * the same sequence in their second entry.
+ *
+ * Ties are broken arbitrarily. See stable_multiway_merge for a variant
+ * that breaks ties by sequence number but is slower.
+ *
+ * The first entries of the pairs (i.e. the begin iterators) will be moved
+ * forward accordingly.
+ *
+ * The output sequence has to provide enough space for all elements
+ * that are written to it.
+ *
+ * This function will merge the input sequences:
+ *
+ * - not stable
+ * - parallel, depending on the input size and Settings
+ * - using sampling for splitting
+ * - using sentinels
+ *
+ * You have to take care that the element the _M_end iterator points to is
+ * readable and contains a value that is greater than any other non-sentinel
+ * value in all sequences.
+ *
+ * Example:
+ *
+ *
+ * int sequences[10][11];
+ * for (int __i = 0; __i < 10; ++__i)
+ * for (int __j = 0; __i < 11; ++__j)
+ * sequences[__i][__j] = __j; // __last one is sentinel!
+ *
+ * int __out[33];
+ * std::vector > seqs;
+ * for (int __i = 0; __i < 10; ++__i)
+ * { seqs.push(std::make_pair(sequences[__i],
+ * sequences[__i] + 10)) }
+ *
+ * multiway_merge(seqs.begin(), seqs.end(), __target, std::less(), 33);
+ *
+ *
+ * @pre All input sequences must be sorted.
+ * @pre Target must provide enough space to merge out length elements or
+ * the number of elements in all sequences, whichever is smaller.
+ * @pre For each @c __i, @c __seqs_begin[__i].second must be the end
+ * marker of the sequence, but also reference the one more __sentinel
+ * element.
+ *
+ * @post [__target, return __value) contains merged __elements from the
+ * input sequences.
+ * @post return __value - __target = min(__length, number of elements in all
+ * sequences).
+ *
+ * @see stable_multiway_merge_sentinels
+ *
+ * @tparam _RAIterPairIterator iterator over sequence
+ * of pairs of iterators
+ * @tparam _RAIterOut iterator over target sequence
+ * @tparam _DifferenceTp difference type for the sequence
+ * @tparam _Compare strict weak ordering type to compare elements
+ * in sequences
+ *
+ * @param __seqs_begin __begin of sequence __sequence
+ * @param __seqs_end _M_end of sequence __sequence
+ * @param __target target sequence to merge to.
+ * @param __comp strict weak ordering to use for element comparison.
+ * @param __length Maximum length to merge, possibly larger than the
+ * number of elements available.
+ *
+ * @return _M_end iterator of output sequence
+ */
+ // multiway_merge_sentinels
+ // public interface
+ template
+ _RAIterOut
+ multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
+ _RAIterPairIterator __seqs_end,
+ _RAIterOut __target,
+ _DifferenceTp __length, _Compare __comp,
+ __gnu_parallel::sequential_tag)
+ {
+ typedef _DifferenceTp _DifferenceType;
+ _GLIBCXX_CALL(__seqs_end - __seqs_begin)
+
+ // catch special case: no sequences
+ if (__seqs_begin == __seqs_end)
+ return __target;
+
+ // Execute multiway merge *sequentially*.
+ return __sequential_multiway_merge
+
+ (__seqs_begin, __seqs_end,
+ __target, *(__seqs_begin->second), __length, __comp);
+ }
+
+ // public interface
+ template
+ _RAIterOut
+ multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
+ _RAIterPairIterator __seqs_end,
+ _RAIterOut __target,
+ _DifferenceTp __length, _Compare __comp,
+ __gnu_parallel::exact_tag __tag)
+ {
+ typedef _DifferenceTp _DifferenceType;
+ _GLIBCXX_CALL(__seqs_end - __seqs_begin)
+
+ // catch special case: no sequences
+ if (__seqs_begin == __seqs_end)
+ return __target;
+
+ // Execute merge; maybe parallel, depending on the number of merged
+ // elements and the number of sequences and global thresholds in
+ // Settings.
+ if ((__seqs_end - __seqs_begin > 1)
+ && _GLIBCXX_PARALLEL_CONDITION(
+ ((__seqs_end - __seqs_begin) >=
+ __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
+ && ((_SequenceIndex)__length >=
+ __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
+ return parallel_multiway_merge
+
+ (__seqs_begin, __seqs_end, __target,
+ multiway_merge_exact_splitting
+ ::value_type*, _Compare, _DifferenceTp>,
+ static_cast<_DifferenceType>(__length), __comp,
+ __tag.__get_num_threads());
+ else
+ return __sequential_multiway_merge
+
+ (__seqs_begin, __seqs_end, __target,
+ *(__seqs_begin->second), __length, __comp);
+ }
+
+ // public interface
+ template
+ _RAIterOut
+ multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
+ _RAIterPairIterator __seqs_end,
+ _RAIterOut __target,
+ _DifferenceTp __length, _Compare __comp,
+ sampling_tag __tag)
+ {
+ typedef _DifferenceTp _DifferenceType;
+ _GLIBCXX_CALL(__seqs_end - __seqs_begin)
+
+ // catch special case: no sequences
+ if (__seqs_begin == __seqs_end)
+ return __target;
+
+ // Execute merge; maybe parallel, depending on the number of merged
+ // elements and the number of sequences and global thresholds in
+ // Settings.
+ if ((__seqs_end - __seqs_begin > 1)
+ && _GLIBCXX_PARALLEL_CONDITION(
+ ((__seqs_end - __seqs_begin) >=
+ __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
+ && ((_SequenceIndex)__length >=
+ __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
+ return parallel_multiway_merge
+
+ (__seqs_begin, __seqs_end, __target,
+ multiway_merge_sampling_splitting
+ ::value_type*, _Compare, _DifferenceTp>,
+ static_cast<_DifferenceType>(__length), __comp,
+ __tag.__get_num_threads());
+ else
+ return __sequential_multiway_merge
+ (
+ __seqs_begin, __seqs_end, __target,
+ *(__seqs_begin->second), __length, __comp);
+ }
+
+ // public interface
+ template
+ _RAIterOut
+ multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
+ _RAIterPairIterator __seqs_end,
+ _RAIterOut __target,
+ _DifferenceTp __length, _Compare __comp,
+ parallel_tag __tag = parallel_tag(0))
+ {
+ return multiway_merge_sentinels
+ (__seqs_begin, __seqs_end, __target, __length, __comp,
+ exact_tag(__tag.__get_num_threads()));
+ }
+
+ // public interface
+ template
+ _RAIterOut
+ multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
+ _RAIterPairIterator __seqs_end,
+ _RAIterOut __target,
+ _DifferenceTp __length, _Compare __comp,
+ default_parallel_tag __tag)
+ {
+ return multiway_merge_sentinels
+ (__seqs_begin, __seqs_end, __target, __length, __comp,
+ exact_tag(__tag.__get_num_threads()));
+ }
+
+ // stable_multiway_merge_sentinels
+ // public interface
+ template
+ _RAIterOut
+ stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
+ _RAIterPairIterator __seqs_end,
+ _RAIterOut __target,
+ _DifferenceTp __length, _Compare __comp,
+ __gnu_parallel::sequential_tag)
+ {
+ typedef _DifferenceTp _DifferenceType;
+ _GLIBCXX_CALL(__seqs_end - __seqs_begin)
+
+ // catch special case: no sequences
+ if (__seqs_begin == __seqs_end)
+ return __target;
+
+ // Execute multiway merge *sequentially*.
+ return __sequential_multiway_merge
+
+ (__seqs_begin, __seqs_end, __target,
+ *(__seqs_begin->second), __length, __comp);
+ }
+
+ // public interface
+ template
+ _RAIterOut
+ stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
+ _RAIterPairIterator __seqs_end,
+ _RAIterOut __target,
+ _DifferenceTp __length, _Compare __comp,
+ __gnu_parallel::exact_tag __tag)
+ {
+ typedef _DifferenceTp _DifferenceType;
+ _GLIBCXX_CALL(__seqs_end - __seqs_begin)
+
+ // catch special case: no sequences
+ if (__seqs_begin == __seqs_end)
+ return __target;
+
+ // Execute merge; maybe parallel, depending on the number of merged
+ // elements and the number of sequences and global thresholds in
+ // Settings.
+ if ((__seqs_end - __seqs_begin > 1)
+ && _GLIBCXX_PARALLEL_CONDITION(
+ ((__seqs_end - __seqs_begin) >=
+ __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
+ && ((_SequenceIndex)__length >=
+ __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
+ return parallel_multiway_merge
+
+ (__seqs_begin, __seqs_end, __target,
+ multiway_merge_exact_splitting
+ ::value_type*, _Compare, _DifferenceTp>,
+ static_cast<_DifferenceType>(__length), __comp,
+ __tag.__get_num_threads());
+ else
+ return __sequential_multiway_merge
+
+ (__seqs_begin, __seqs_end, __target,
+ *(__seqs_begin->second), __length, __comp);
+ }
+
+ // public interface
+ template
+ _RAIterOut
+ stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
+ _RAIterPairIterator __seqs_end,
+ _RAIterOut __target,
+ _DifferenceTp __length,
+ _Compare __comp,
+ sampling_tag __tag)
+ {
+ typedef _DifferenceTp _DifferenceType;
+ _GLIBCXX_CALL(__seqs_end - __seqs_begin)
+
+ // catch special case: no sequences
+ if (__seqs_begin == __seqs_end)
+ return __target;
+
+ // Execute merge; maybe parallel, depending on the number of merged
+ // elements and the number of sequences and global thresholds in
+ // Settings.
+ if ((__seqs_end - __seqs_begin > 1)
+ && _GLIBCXX_PARALLEL_CONDITION(
+ ((__seqs_end - __seqs_begin) >=
+ __gnu_parallel::_Settings::get().multiway_merge_minimal_k)
+ && ((_SequenceIndex)__length >=
+ __gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
+ return parallel_multiway_merge
+
+ (__seqs_begin, __seqs_end, __target,
+ multiway_merge_sampling_splitting
+ ::value_type*, _Compare, _DifferenceTp>,
+ static_cast<_DifferenceType>(__length), __comp,
+ __tag.__get_num_threads());
+ else
+ return __sequential_multiway_merge
+
+ (__seqs_begin, __seqs_end, __target,
+ *(__seqs_begin->second), __length, __comp);
+ }
+
+ // public interface
+ template
+ _RAIterOut
+ stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
+ _RAIterPairIterator __seqs_end,
+ _RAIterOut __target,
+ _DifferenceTp __length,
+ _Compare __comp,
+ parallel_tag __tag = parallel_tag(0))
+ {
+ return stable_multiway_merge_sentinels
+ (__seqs_begin, __seqs_end, __target, __length, __comp,
+ exact_tag(__tag.__get_num_threads()));
+ }
+
+ // public interface
+ template
+ _RAIterOut
+ stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
+ _RAIterPairIterator __seqs_end,
+ _RAIterOut __target,
+ _DifferenceTp __length, _Compare __comp,
+ default_parallel_tag __tag)
+ {
+ return stable_multiway_merge_sentinels
+ (__seqs_begin, __seqs_end, __target, __length, __comp,
+ exact_tag(__tag.__get_num_threads()));
+ }
+}; // namespace __gnu_parallel
+
+#endif /* _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H */