path: root/libstdc++-v3/include/parallel/multiway_merge.h

// -*- C++ -*-

// Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the terms
// of the GNU General Public License as published by the Free Software
// Foundation; either version 3, or (at your option) any later
// version.

// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.

/** @file parallel/multiway_merge.h
*  @brief Implementation of sequential and parallel multiway merge.
*
*  Explanations on the high-speed merging routines in the appendix of
*
*  P. Sanders.
*  Fast priority queues for cached memory.
*  ACM Journal of Experimental Algorithmics, 5, 2000.
*
*  This file is a GNU parallel extension to the Standard C++ Library.
*/

// Written by Johannes Singler and Manuel Holtgrewe.

#ifndef _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H
#define _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H

#include <vector>

#include <bits/stl_algo.h>
#include <parallel/features.h>
#include <parallel/parallel.h>
#include <parallel/losertree.h>
#if _GLIBCXX_ASSERTIONS
#include <parallel/checkers.h>
#endif

/** @brief Length of a sequence described by a pair of iterators. */
#define _GLIBCXX_PARALLEL_LENGTH(__s) ((__s).second - (__s).first)

namespace __gnu_parallel
{

// Announce guarded and unguarded iterator.

template<typename _RAIter, typename _Compare>
  class _GuardedIterator;

// Making the arguments const references seems to dangerous,
// the user-defined comparator might not be const.
template<typename _RAIter, typename _Compare>
  inline bool
  operator<(_GuardedIterator<_RAIter, _Compare>& __bi1,
             _GuardedIterator<_RAIter, _Compare>& __bi2);

template<typename _RAIter, typename _Compare>
  inline bool
  operator<=(_GuardedIterator<_RAIter, _Compare>& __bi1,
              _GuardedIterator<_RAIter, _Compare>& __bi2);

/** @brief _Iterator wrapper supporting an implicit supremum at the end
 *         of the sequence, dominating all comparisons.
 *
 * The implicit supremum comes with __a performance cost.
 *
 * Deriving from _RAIter is not possible since
 * _RAIter need not be a class.
 */
template<typename _RAIter, typename _Compare>
  class _GuardedIterator
  {
  private:
    /** @brief Current iterator __position. */
    _RAIter _M_current;

    /** @brief End iterator of the sequence. */
    _RAIter _M_end;

    /** @brief _Compare. */
    _Compare& __comp;

  public:
    /** @brief Constructor. Sets iterator to beginning of sequence.
    *  @param __begin Begin iterator of sequence.
    *  @param _M_end End iterator of sequence.
    *  @param __comp Comparator provided for associated overloaded
    *  compare operators. */
    _GuardedIterator(_RAIter __begin,
                     _RAIter _M_end, _Compare& __comp)
    : _M_current(__begin), _M_end(_M_end), __comp(__comp)
    { }

    /** @brief Pre-increment operator.
    *  @return This. */
    _GuardedIterator<_RAIter, _Compare>&
    operator++()
    {
      ++_M_current;
      return *this;
    }

    /** @brief Dereference operator.
    *  @return Referenced element. */
    typename std::iterator_traits<_RAIter>::value_type&
    operator*()
    { return *_M_current; }

    /** @brief Convert to wrapped iterator.
    *  @return Wrapped iterator. */
    operator _RAIter()
    { return _M_current; }

    friend bool
    operator< <_RAIter, _Compare>(
      _GuardedIterator<_RAIter, _Compare>& __bi1,
      _GuardedIterator<_RAIter, _Compare>& __bi2);

    friend bool
    operator<= <_RAIter, _Compare>(
      _GuardedIterator<_RAIter, _Compare>& __bi1,
      _GuardedIterator<_RAIter, _Compare>& __bi2);
  };

/** @brief Compare two elements referenced by guarded iterators.
 *  @param __bi1 First iterator.
 *  @param __bi2 Second iterator.
 *  @return @__c true if less. */
template<typename _RAIter, typename _Compare>
  inline bool
  operator<(_GuardedIterator<_RAIter, _Compare>& __bi1,
            _GuardedIterator<_RAIter, _Compare>& __bi2)
  {
    if (__bi1._M_current == __bi1._M_end)	//__bi1 is sup
      return __bi2._M_current == __bi2._M_end;	//__bi2 is not sup
    if (__bi2._M_current == __bi2._M_end)	//__bi2 is sup
      return true;
    return (__bi1.__comp)(*__bi1, *__bi2);	//normal compare
  }

/** @brief Compare two elements referenced by guarded iterators.
 *  @param __bi1 First iterator.
 *  @param __bi2 Second iterator.
 *  @return @__c True if less equal. */
template<typename _RAIter, typename _Compare>
  inline bool
  operator<=(_GuardedIterator<_RAIter, _Compare>& __bi1,
               _GuardedIterator<_RAIter, _Compare>& __bi2)
  {
    if (__bi2._M_current == __bi2._M_end)	//__bi1 is sup
      return __bi1._M_current != __bi1._M_end;	//__bi2 is not sup
    if (__bi1._M_current == __bi1._M_end)	//__bi2 is sup
      return false;
    return !(__bi1.__comp)(*__bi2, *__bi1);	//normal compare
  }

template<typename _RAIter, typename _Compare>
  class unguarded_iterator;

template<typename _RAIter, typename _Compare>
  inline bool
  operator<(unguarded_iterator<_RAIter, _Compare>& __bi1,
            unguarded_iterator<_RAIter, _Compare>& __bi2);

template<typename _RAIter, typename _Compare>
  inline bool
  operator<=(unguarded_iterator<_RAIter, _Compare>& __bi1,
             unguarded_iterator<_RAIter, _Compare>& __bi2);

template<typename _RAIter, typename _Compare>
  class unguarded_iterator
  {
  private:
    /** @brief Current iterator __position. */
    _RAIter _M_current;
    /** @brief _Compare. */
    mutable _Compare& __comp;

  public:
    /** @brief Constructor. Sets iterator to beginning of sequence.
    *  @param __begin Begin iterator of sequence.
    *  @param _M_end Unused, only for compatibility.
    *  @param __comp Unused, only for compatibility. */
    unguarded_iterator(_RAIter __begin,
                       _RAIter _M_end, _Compare& __comp)
    : _M_current(__begin), __comp(__comp)
    { }

    /** @brief Pre-increment operator.
    *  @return This. */
    unguarded_iterator<_RAIter, _Compare>&
    operator++()
    {
      ++_M_current;
      return *this;
    }

    /** @brief Dereference operator.
    *  @return Referenced element. */
    typename std::iterator_traits<_RAIter>::value_type&
    operator*()
    { return *_M_current; }

    /** @brief Convert to wrapped iterator.
    *  @return Wrapped iterator. */
    operator _RAIter()
    { return _M_current; }

    friend bool
    operator< <_RAIter, _Compare>(
      unguarded_iterator<_RAIter, _Compare>& __bi1,
      unguarded_iterator<_RAIter, _Compare>& __bi2);

    friend bool
    operator<= <_RAIter, _Compare>(
      unguarded_iterator<_RAIter, _Compare>& __bi1,
      unguarded_iterator<_RAIter, _Compare>& __bi2);
  };

/** @brief Compare two elements referenced by unguarded iterators.
 *  @param __bi1 First iterator.
 *  @param __bi2 Second iterator.
 *  @return @__c true if less. */
template<typename _RAIter, typename _Compare>
  inline bool
  operator<(unguarded_iterator<_RAIter, _Compare>& __bi1,
            unguarded_iterator<_RAIter, _Compare>& __bi2)
  {
    // Normal compare.
    return (__bi1.__comp)(*__bi1, *__bi2);
  }

/** @brief Compare two elements referenced by unguarded iterators.
 *  @param __bi1 First iterator.
 *  @param __bi2 Second iterator.
 *  @return @__c True if less equal. */
template<typename _RAIter, typename _Compare>
  inline bool
  operator<=(unguarded_iterator<_RAIter, _Compare>& __bi1,
            unguarded_iterator<_RAIter, _Compare>& __bi2)
  {
    // Normal compare.
    return !(__bi1.__comp)(*__bi2, *__bi1);
  }

/** @brief Highly efficient 3-way merging procedure.
 *
 * Merging is done with the algorithm implementation described by Peter
 * Sanders.  Basically, the idea is to minimize the number of necessary
 * comparison after merging an element.  The implementation trick
 * that makes this fast is that the order of the sequences is stored
 * in the instruction pointer (translated into labels in C++).
 *
 * This works well for merging up to 4 sequences.
 *
 * Note that making the merging stable does <em>not</em> come at __a
 * performance hit.
 *
 * Whether the merging is done guarded or unguarded is selected by the
 * used iterator class.
 *
 * @param __seqs_begin Begin iterator of iterator pair input sequence.
 * @param __seqs_end End iterator of iterator pair input sequence.
 * @param __target Begin iterator of __output sequence.
 * @param __comp Comparator.
 * @param __length Maximum length to merge, less equal than the
 * total number of elements available.
 *
 * @return End iterator of output sequence.
 */
template<template<typename RAI, typename C> class iterator,
	 typename _RAIterIterator,
	 typename _RAIter3,
	 typename _DifferenceTp,
	 typename _Compare>
  _RAIter3
  multiway_merge_3_variant(
      _RAIterIterator __seqs_begin,
      _RAIterIterator __seqs_end,
      _RAIter3 __target,
      _DifferenceTp __length, _Compare __comp)
  {
    _GLIBCXX_CALL(__length);

    typedef _DifferenceTp _DifferenceType;

    typedef typename std::iterator_traits<_RAIterIterator>
      ::value_type::first_type
      _RAIter1;
    typedef typename std::iterator_traits<_RAIter1>::value_type
      _ValueType;

    if (__length == 0)
      return __target;

#if _GLIBCXX_ASSERTIONS
    _DifferenceTp orig_length = __length;
#endif

    iterator<_RAIter1, _Compare>
      __seq0(__seqs_begin[0].first, __seqs_begin[0].second, __comp),
      __seq1(__seqs_begin[1].first, __seqs_begin[1].second, __comp),
      __seq2(__seqs_begin[2].first, __seqs_begin[2].second, __comp);

    if (__seq0 <= __seq1)
      {
        if (__seq1 <= __seq2)
          goto __s012;
        else
          if (__seq2 <  __seq0)
            goto __s201;
          else
            goto __s021;
      }
    else
      {
        if (__seq1 <= __seq2)
          {
            if (__seq0 <= __seq2)
              goto __s102;
            else
              goto __s120;
          }
        else
          goto __s210;
      }
#define _GLIBCXX_PARALLEL_MERGE_3_CASE(__a,__b,__c,c0,c1)     \
    __s ## __a ## __b ## __c :                                  \
      *__target = *__seq ## __a;                              \
      ++__target;                                         \
      --__length;                                         \
      ++__seq ## __a;                                       \
      if (__length == 0) goto finish;                     \
      if (__seq ## __a c0 __seq ## __b) goto __s ## __a ## __b ## __c;  \
      if (__seq ## __a c1 __seq ## __c) goto __s ## __b ## __a ## __c;  \
      goto __s ## __b ## __c ## __a;

    _GLIBCXX_PARALLEL_MERGE_3_CASE(0, 1, 2, <=, <=);
    _GLIBCXX_PARALLEL_MERGE_3_CASE(1, 2, 0, <=, < );
    _GLIBCXX_PARALLEL_MERGE_3_CASE(2, 0, 1, < , < );
    _GLIBCXX_PARALLEL_MERGE_3_CASE(1, 0, 2, < , <=);
    _GLIBCXX_PARALLEL_MERGE_3_CASE(0, 2, 1, <=, <=);
    _GLIBCXX_PARALLEL_MERGE_3_CASE(2, 1, 0, < , < );

#undef _GLIBCXX_PARALLEL_MERGE_3_CASE

  finish:
    ;

#if _GLIBCXX_ASSERTIONS
  _GLIBCXX_PARALLEL_ASSERT(
      ((_RAIter1)__seq0 - __seqs_begin[0].first) +
      ((_RAIter1)__seq1 - __seqs_begin[1].first) +
      ((_RAIter1)__seq2 - __seqs_begin[2].first)
      == orig_length);
#endif

    __seqs_begin[0].first = __seq0;
    __seqs_begin[1].first = __seq1;
    __seqs_begin[2].first = __seq2;

    return __target;
  }

/**
 * @brief Highly efficient 4-way merging procedure.
 *
 * Merging is done with the algorithm implementation described by Peter
 * Sanders. Basically, the idea is to minimize the number of necessary
 * comparison after merging an element.  The implementation trick
 * that makes this fast is that the order of the sequences is stored
 * in the instruction pointer (translated into goto labels in C++).
 *
 * This works well for merging up to 4 sequences.
 *
 * Note that making the merging stable does <em>not</em> come at __a
 * performance hit.
 *
 * Whether the merging is done guarded or unguarded is selected by the
 * used iterator class.
 *
 * @param __seqs_begin Begin iterator of iterator pair input sequence.
 * @param __seqs_end End iterator of iterator pair input sequence.
 * @param __target Begin iterator of __output sequence.
 * @param __comp Comparator.
 * @param __length Maximum length to merge, less equal than the
 * total number of elements available.
 *
 * @return End iterator of output sequence.
 */
template<template<typename RAI, typename C> class iterator,
	 typename _RAIterIterator,
	 typename _RAIter3,
	 typename _DifferenceTp,
	 typename _Compare>
  _RAIter3
  multiway_merge_4_variant(_RAIterIterator __seqs_begin,
                           _RAIterIterator __seqs_end,
                           _RAIter3 __target,
                           _DifferenceTp __length, _Compare __comp)
  {
    _GLIBCXX_CALL(__length);
    typedef _DifferenceTp _DifferenceType;

    typedef typename std::iterator_traits<_RAIterIterator>
      ::value_type::first_type
      _RAIter1;
    typedef typename std::iterator_traits<_RAIter1>::value_type
      _ValueType;

    iterator<_RAIter1, _Compare>
      __seq0(__seqs_begin[0].first, __seqs_begin[0].second, __comp),
      __seq1(__seqs_begin[1].first, __seqs_begin[1].second, __comp),
      __seq2(__seqs_begin[2].first, __seqs_begin[2].second, __comp),
      __seq3(__seqs_begin[3].first, __seqs_begin[3].second, __comp);

#define _GLIBCXX_PARALLEL_DECISION(__a,__b,__c,d) {                   \
      if (__seq ## d < __seq ## __a) goto __s ## d ## __a ## __b ## __c;	\
      if (__seq ## d < __seq ## __b) goto __s ## __a ## d ## __b ## __c;	\
      if (__seq ## d < __seq ## __c) goto __s ## __a ## __b ## d ## __c;	\
      goto __s ## __a ## __b ## __c ## d;  }

    if (__seq0 <= __seq1)
      {
        if (__seq1 <= __seq2)
          _GLIBCXX_PARALLEL_DECISION(0,1,2,3)
          else
            if (__seq2 < __seq0)
              _GLIBCXX_PARALLEL_DECISION(2,0,1,3)
              else
                _GLIBCXX_PARALLEL_DECISION(0,2,1,3)
                  }
    else
      {
        if (__seq1 <= __seq2)
          {
            if (__seq0 <= __seq2)
              _GLIBCXX_PARALLEL_DECISION(1,0,2,3)
              else
                _GLIBCXX_PARALLEL_DECISION(1,2,0,3)
                  }
        else
          _GLIBCXX_PARALLEL_DECISION(2,1,0,3)
            }

#define _GLIBCXX_PARALLEL_MERGE_4_CASE(__a,__b,__c,d,c0,c1,c2)        \
    __s ## __a ## __b ## __c ## d:                                      \
      if (__length == 0) goto finish;                             \
    *__target = *__seq ## __a;                                        \
    ++__target;                                                   \
    --__length;                                                   \
    ++__seq ## __a;                                                 \
    if (__seq ## __a c0 __seq ## __b) goto __s ## __a ## __b ## __c ## d;       \
    if (__seq ## __a c1 __seq ## __c) goto __s ## __b ## __a ## __c ## d;       \
    if (__seq ## __a c2 __seq ## d) goto __s ## __b ## __c ## __a ## d;       \
    goto __s ## __b ## __c ## d ## __a;

    _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 1, 2, 3, <=, <=, <=);
    _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 1, 3, 2, <=, <=, <=);
    _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 2, 1, 3, <=, <=, <=);
    _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 2, 3, 1, <=, <=, <=);
    _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 3, 1, 2, <=, <=, <=);
    _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 3, 2, 1, <=, <=, <=);
    _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 0, 2, 3, < , <=, <=);
    _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 0, 3, 2, < , <=, <=);
    _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 2, 0, 3, <=, < , <=);
    _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 2, 3, 0, <=, <=, < );
    _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 3, 0, 2, <=, < , <=);
    _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 3, 2, 0, <=, <=, < );
    _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 0, 1, 3, < , < , <=);
    _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 0, 3, 1, < , <=, < );
    _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 1, 0, 3, < , < , <=);
    _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 1, 3, 0, < , <=, < );
    _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 3, 0, 1, <=, < , < );
    _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 3, 1, 0, <=, < , < );
    _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 0, 1, 2, < , < , < );
    _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 0, 2, 1, < , < , < );
    _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 1, 0, 2, < , < , < );
    _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 1, 2, 0, < , < , < );
    _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 2, 0, 1, < , < , < );
    _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 2, 1, 0, < , < , < );

#undef _GLIBCXX_PARALLEL_MERGE_4_CASE
#undef _GLIBCXX_PARALLEL_DECISION

  finish:
    ;

    __seqs_begin[0].first = __seq0;
    __seqs_begin[1].first = __seq1;
    __seqs_begin[2].first = __seq2;
    __seqs_begin[3].first = __seq3;

    return __target;
  }

/** @brief Multi-way merging procedure for a high branching factor,
 *         guarded case.
 *
 * This merging variant uses __a LoserTree class as selected by <tt>LT</tt>.
 *
 * Stability is selected through the used LoserTree class <tt>LT</tt>.
 *
 * At least one non-empty __sequence is required.
 *
 * @param __seqs_begin Begin iterator of iterator pair input sequence.
 * @param __seqs_end End iterator of iterator pair input sequence.
 * @param __target Begin iterator of __output sequence.
 * @param __comp Comparator.
 * @param __length Maximum length to merge, less equal than the
 * total number of elements available.
 *
 * @return End iterator of output sequence.
 */
template<typename LT,
	 typename _RAIterIterator,
	 typename _RAIter3,
	 typename _DifferenceTp,
	 typename _Compare>
  _RAIter3
  multiway_merge_loser_tree(_RAIterIterator __seqs_begin,
                            _RAIterIterator __seqs_end,
                            _RAIter3 __target,
                            _DifferenceTp __length, _Compare __comp)
  {
    _GLIBCXX_CALL(__length)

    typedef _DifferenceTp _DifferenceType;
    typedef typename std::iterator_traits<_RAIterIterator>
      ::value_type::first_type
      _RAIter1;
    typedef typename std::iterator_traits<_RAIter1>::value_type
      _ValueType;

    int __k = static_cast<int>(__seqs_end - __seqs_begin);

    LT __lt(__k, __comp);

    // Default value for potentially non-default-constructible types.
    _ValueType* __arbitrary_element = NULL;

    for (int __t = 0; __t < __k; ++__t)
      {
        if(__arbitrary_element == NULL
            && _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__t]) > 0)
          __arbitrary_element = &(*__seqs_begin[__t].first);
      }

    for (int __t = 0; __t < __k; ++__t)
      {
        if (__seqs_begin[__t].first == __seqs_begin[__t].second)
          __lt.__insert_start(*__arbitrary_element, __t, true);
        else
          __lt.__insert_start(*__seqs_begin[__t].first, __t, false);
      }

    __lt.__init();

    int source;

    for (_DifferenceType __i = 0; __i < __length; ++__i)
      {
        //take out
        source = __lt.__get_min_source();

        *(__target++) = *(__seqs_begin[source].first++);

        // Feed.
        if (__seqs_begin[source].first == __seqs_begin[source].second)
          __lt.__delete_min_insert(*__arbitrary_element, true);
        else
          // Replace from same source.
          __lt.__delete_min_insert(*__seqs_begin[source].first, false);
      }

    return __target;
  }

/** @brief Multi-way merging procedure for a high branching factor,
 *         unguarded case.
 *
 * Merging is done using the LoserTree class <tt>LT</tt>.
 *
 * Stability is selected by the used LoserTrees.
 *
 * @pre No input will run out of elements during the merge.
 *
 * @param __seqs_begin Begin iterator of iterator pair input sequence.
 * @param __seqs_end End iterator of iterator pair input sequence.
 * @param __target Begin iterator of __output sequence.
 * @param __comp Comparator.
 * @param __length Maximum length to merge, less equal than the
 * total number of elements available.
 *
 * @return End iterator of output sequence.
 */
template<typename LT,
    typename _RAIterIterator,
    typename _RAIter3,
    typename _DifferenceTp, typename _Compare>
  _RAIter3
  multiway_merge_loser_tree_unguarded(
    _RAIterIterator __seqs_begin,
    _RAIterIterator __seqs_end,
    _RAIter3 __target,
    const typename std::iterator_traits<typename std::iterator_traits<
      _RAIterIterator>::value_type::first_type>::value_type&
        __sentinel,
    _DifferenceTp __length,
    _Compare __comp)
  {
    _GLIBCXX_CALL(__length)
    typedef _DifferenceTp _DifferenceType;

    typedef typename std::iterator_traits<_RAIterIterator>
      ::value_type::first_type
      _RAIter1;
    typedef typename std::iterator_traits<_RAIter1>::value_type
      _ValueType;

    int __k = __seqs_end - __seqs_begin;

    LT __lt(__k, __sentinel, __comp);

    for (int __t = 0; __t < __k; ++__t)
      {
#if _GLIBCXX_ASSERTIONS
        _GLIBCXX_PARALLEL_ASSERT(__seqs_begin[__t].first != __seqs_begin[__t].second);
#endif
        __lt.__insert_start(*__seqs_begin[__t].first, __t, false);
      }

    __lt.__init();

    int source;

#if _GLIBCXX_ASSERTIONS
    _DifferenceType __i = 0;
#endif

    _RAIter3 __target_end = __target + __length;
    while (__target < __target_end)
      {
        // Take out.
        source = __lt.__get_min_source();

#if _GLIBCXX_ASSERTIONS
        _GLIBCXX_PARALLEL_ASSERT(0 <= source && source < __k);
        _GLIBCXX_PARALLEL_ASSERT(__i == 0
            || !__comp(*(__seqs_begin[source].first), *(__target - 1)));
#endif

        // Feed.
        *(__target++) = *(__seqs_begin[source].first++);

#if _GLIBCXX_ASSERTIONS
        ++__i;
#endif
        // Replace from same source.
        __lt.__delete_min_insert(*__seqs_begin[source].first, false);
      }

    return __target;
  }


/** @brief Multi-way merging procedure for a high branching factor,
 *         requiring sentinels to exist.
 *
 * @param __stable The value must the same as for the used LoserTrees.
 * @param UnguardedLoserTree _Loser Tree variant to use for the unguarded
 *   merging.
 * @param GuardedLoserTree _Loser Tree variant to use for the guarded
 *   merging.
 *
 * @param __seqs_begin Begin iterator of iterator pair input sequence.
 * @param __seqs_end End iterator of iterator pair input sequence.
 * @param __target Begin iterator of __output sequence.
 * @param __comp Comparator.
 * @param __length Maximum length to merge, less equal than the
 * total number of elements available.
 *
 * @return End iterator of output sequence.
 */
template<
    typename UnguardedLoserTree,
    typename _RAIterIterator,
    typename _RAIter3,
    typename _DifferenceTp,
    typename _Compare>
  _RAIter3
  multiway_merge_loser_tree_sentinel(
    _RAIterIterator __seqs_begin,
    _RAIterIterator __seqs_end,
    _RAIter3 __target,
    const typename std::iterator_traits<typename std::iterator_traits<
      _RAIterIterator>::value_type::first_type>::value_type&
        __sentinel,
    _DifferenceTp __length,
    _Compare __comp)
  {
    _GLIBCXX_CALL(__length)

    typedef _DifferenceTp _DifferenceType;
    typedef std::iterator_traits<_RAIterIterator> _TraitsType;
    typedef typename std::iterator_traits<_RAIterIterator>
      ::value_type::first_type
      _RAIter1;
    typedef typename std::iterator_traits<_RAIter1>::value_type
      _ValueType;

    _RAIter3 __target_end;

    for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s)
      // Move the sequends _M_end behind the sentinel spots.  This has the
      // effect that the sentinel appears to be within the sequence. Then,
      // we can use the unguarded variant if we merge out as many
      // non-sentinel elements as we have.
      ++((*__s).second);

    __target_end = multiway_merge_loser_tree_unguarded
        <UnguardedLoserTree>
      (__seqs_begin, __seqs_end, __target, __sentinel, __length, __comp);

#if _GLIBCXX_ASSERTIONS
    _GLIBCXX_PARALLEL_ASSERT(__target_end == __target + __length);
    _GLIBCXX_PARALLEL_ASSERT(__is_sorted(__target, __target_end, __comp));
#endif

    // Restore the sequence ends so the sentinels are not contained in the
    // sequence any more (see comment in loop above).
    for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s)
      --((*__s).second);

    return __target_end;
  }

/**
 * @brief Traits for determining whether the loser tree should
 *   use pointers or copies.
 *
 * The field "_M_use_pointer" is used to determine whether to use pointers in
 * the loser trees or whether to copy the values into the loser tree.
 *
 * The default behavior is to use pointers if the data type is 4 times as
 * big as the pointer to it.
 *
 * Specialize for your data type to customize the behavior.
 *
 * Example:
 *
 *   template<>
 *   struct _LoserTreeTraits<int>
 *   { static const bool _M_use_pointer = false; };
 *
 *   template<>
 *   struct _LoserTreeTraits<heavyweight_type>
 *   { static const bool _M_use_pointer = true; };
 *
 * @param _Tp type to give the loser tree traits for.
 */
template <typename _Tp>
struct _LoserTreeTraits
{
  /**
   * @brief True iff to use pointers instead of values in loser trees.
   *
   * The default behavior is to use pointers if the data type is four
   * times as big as the pointer to it.
   */
  static const bool _M_use_pointer = (sizeof(_Tp) > 4 * sizeof(_Tp*));
};

/**
 * @brief Switch for 3-way merging with __sentinels turned off.
 *
 * Note that 3-way merging is always stable!
 */
template<
  bool __sentinels /*default == false*/,
  typename _RAIterIterator,
  typename _RAIter3,
  typename _DifferenceTp,
  typename _Compare>
struct __multiway_merge_3_variant_sentinel_switch
{
  _RAIter3 operator()(
      _RAIterIterator __seqs_begin,
      _RAIterIterator __seqs_end,
      _RAIter3 __target,
      _DifferenceTp __length, _Compare __comp)
  {
    return multiway_merge_3_variant<_GuardedIterator>(
        __seqs_begin, __seqs_end, __target, __length, __comp);
  }
};

/**
 * @brief Switch for 3-way merging with __sentinels turned on.
 *
 * Note that 3-way merging is always stable!
 */
template<
  typename _RAIterIterator,
  typename _RAIter3,
  typename _DifferenceTp,
  typename _Compare>
struct __multiway_merge_3_variant_sentinel_switch
    <true, _RAIterIterator, _RAIter3,
     _DifferenceTp, _Compare>
{
  _RAIter3 operator()(
      _RAIterIterator __seqs_begin,
      _RAIterIterator __seqs_end,
      _RAIter3 __target,
      _DifferenceTp __length, _Compare __comp)
  {
    return multiway_merge_3_variant<unguarded_iterator>(
        __seqs_begin, __seqs_end, __target, __length, __comp);
  }
};

/**
 * @brief Switch for 4-way merging with __sentinels turned off.
 *
 * Note that 4-way merging is always stable!
 */
template<
  bool __sentinels /*default == false*/,
  typename _RAIterIterator,
  typename _RAIter3,
  typename _DifferenceTp,
  typename _Compare>
struct __multiway_merge_4_variant_sentinel_switch
{
  _RAIter3 operator()(
      _RAIterIterator __seqs_begin,
      _RAIterIterator __seqs_end,
      _RAIter3 __target,
      _DifferenceTp __length, _Compare __comp)
  {
    return multiway_merge_4_variant<_GuardedIterator>(
        __seqs_begin, __seqs_end, __target, __length, __comp);
  }
};

/**
 * @brief Switch for 4-way merging with __sentinels turned on.
 *
 * Note that 4-way merging is always stable!
 */
template<
  typename _RAIterIterator,
  typename _RAIter3,
  typename _DifferenceTp,
  typename _Compare>
struct __multiway_merge_4_variant_sentinel_switch
    <true, _RAIterIterator, _RAIter3,
     _DifferenceTp, _Compare>
{
  _RAIter3 operator()(
      _RAIterIterator __seqs_begin,
      _RAIterIterator __seqs_end,
      _RAIter3 __target,
      _DifferenceTp __length, _Compare __comp)
  {
    return multiway_merge_4_variant<unguarded_iterator>(
        __seqs_begin, __seqs_end, __target, __length, __comp);
  }
};

/**
 * @brief Switch for k-way merging with __sentinels turned on.
 */
template<
  bool __sentinels,
  bool __stable,
  typename _RAIterIterator,
  typename _RAIter3,
  typename _DifferenceTp,
  typename _Compare>
struct __multiway_merge_k_variant_sentinel_switch
{
  _RAIter3 operator()(
      _RAIterIterator __seqs_begin,
      _RAIterIterator __seqs_end,
      _RAIter3 __target,
      const typename std::iterator_traits<typename std::iterator_traits<
        _RAIterIterator>::value_type::first_type>::value_type&
          __sentinel,
      _DifferenceTp __length, _Compare __comp)
  {
    typedef typename std::iterator_traits<_RAIterIterator>
      ::value_type::first_type
      _RAIter1;
    typedef typename std::iterator_traits<_RAIter1>::value_type
      _ValueType;

    return multiway_merge_loser_tree_sentinel<
        typename __gnu_cxx::__conditional_type<
            _LoserTreeTraits<_ValueType>::_M_use_pointer
          , LoserTreePointerUnguarded<__stable, _ValueType, _Compare>
          , _LoserTreeUnguarded<__stable, _ValueType, _Compare>
        >::__type>(__seqs_begin, __seqs_end, __target, __sentinel, __length, __comp);
  }
};

/**
 * @brief Switch for k-way merging with __sentinels turned off.
 */
template<
  bool __stable,
  typename _RAIterIterator,
  typename _RAIter3,
  typename _DifferenceTp,
  typename _Compare>
struct __multiway_merge_k_variant_sentinel_switch
    <false, __stable, _RAIterIterator, _RAIter3,
     _DifferenceTp, _Compare>
{
  _RAIter3 operator()(
      _RAIterIterator __seqs_begin,
      _RAIterIterator __seqs_end,
      _RAIter3 __target,
      const typename std::iterator_traits<typename std::iterator_traits<
        _RAIterIterator>::value_type::first_type>::value_type&
          __sentinel,
      _DifferenceTp __length, _Compare __comp)
  {
    typedef typename std::iterator_traits<_RAIterIterator>
      ::value_type::first_type
      _RAIter1;
    typedef typename std::iterator_traits<_RAIter1>::value_type
      _ValueType;

    return multiway_merge_loser_tree<
        typename __gnu_cxx::__conditional_type<
            _LoserTreeTraits<_ValueType>::_M_use_pointer
          , _LoserTreePointer<__stable, _ValueType, _Compare>
          , _LoserTree<__stable, _ValueType, _Compare>
        >::__type >(__seqs_begin, __seqs_end, __target, __length, __comp);
  }
};

/** @brief Sequential multi-way merging switch.
 *
 *  The _GLIBCXX_PARALLEL_DECISION is based on the branching factor and
 *  runtime settings.
 *  @param __seqs_begin Begin iterator of iterator pair input sequence.
 *  @param __seqs_end End iterator of iterator pair input sequence.
 *  @param __target Begin iterator of __output sequence.
 *  @param __comp Comparator.
 *  @param __length Maximum length to merge, possibly larger than the
 *  number of elements available.
 *  @param __stable Stable merging incurs __a performance penalty.
 *  @param __sentinel The sequences have __a __sentinel element.
 *  @return End iterator of output sequence. */
template<
    bool __stable,
    bool __sentinels,
    typename _RAIterIterator,
    typename _RAIter3,
    typename _DifferenceTp,
    typename _Compare>
  _RAIter3
  __sequential_multiway_merge(
    _RAIterIterator __seqs_begin,
    _RAIterIterator __seqs_end,
    _RAIter3 __target,
    const typename std::iterator_traits<typename std::iterator_traits<
      _RAIterIterator>::value_type::first_type>::value_type&
        __sentinel,
    _DifferenceTp __length, _Compare __comp)
  {
    _GLIBCXX_CALL(__length)

    typedef _DifferenceTp _DifferenceType;
    typedef typename std::iterator_traits<_RAIterIterator>
      ::value_type::first_type
      _RAIter1;
    typedef typename std::iterator_traits<_RAIter1>::value_type
      _ValueType;

#if _GLIBCXX_ASSERTIONS
    for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s)
      {
        _GLIBCXX_PARALLEL_ASSERT(__is_sorted((*__s).first, (*__s).second, __comp));
      }
#endif

    _DifferenceTp __total_length = 0;
    for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s)
      __total_length += _GLIBCXX_PARALLEL_LENGTH(*__s);

    __length = std::min<_DifferenceTp>(__length, __total_length);

    if(__length == 0)
      return __target;

    _RAIter3 __return_target = __target;
    int __k = static_cast<int>(__seqs_end - __seqs_begin);

    switch (__k)
      {
      case 0:
        break;
      case 1:
        __return_target = std::copy(__seqs_begin[0].first,
                                  __seqs_begin[0].first + __length,
                                  __target);
        __seqs_begin[0].first += __length;
        break;
      case 2:
        __return_target = __merge_advance(__seqs_begin[0].first,
                                      __seqs_begin[0].second,
                                      __seqs_begin[1].first,
                                      __seqs_begin[1].second,
                                      __target, __length, __comp);
        break;
      case 3:
        __return_target = __multiway_merge_3_variant_sentinel_switch<
            __sentinels
          , _RAIterIterator
          , _RAIter3
          , _DifferenceTp
          , _Compare>()(__seqs_begin, __seqs_end, __target, __length, __comp);
        break;
      case 4:
        __return_target = __multiway_merge_4_variant_sentinel_switch<
            __sentinels
          , _RAIterIterator
          , _RAIter3
          , _DifferenceTp
          , _Compare>()(__seqs_begin, __seqs_end, __target, __length, __comp);
        break;
      default:
          __return_target = __multiway_merge_k_variant_sentinel_switch<
              __sentinels
            , __stable
            , _RAIterIterator
            , _RAIter3
            , _DifferenceTp
            , _Compare>()(__seqs_begin, __seqs_end, __target, __sentinel, __length, __comp);
          break;
      }
#if _GLIBCXX_ASSERTIONS
    _GLIBCXX_PARALLEL_ASSERT(__is_sorted(__target, __target + __length, __comp));
#endif

    return __return_target;
  }

/**
 * @brief Stable sorting functor.
 *
 * Used to reduce code instanciation in multiway_merge_sampling_splitting.
 */
template<bool __stable, class _RAIter, class _StrictWeakOrdering>
struct _SamplingSorter
{
  void operator()(_RAIter __first, _RAIter __last,
                  _StrictWeakOrdering __comp)
  { __gnu_sequential::stable_sort(__first, __last, __comp); }
};

/**
 * @brief Non-__stable sorting functor.
 *
 * Used to reduce code instantiation in multiway_merge_sampling_splitting.
 */
template<class _RAIter, class _StrictWeakOrdering>
struct _SamplingSorter<false, _RAIter, _StrictWeakOrdering>
{
  void operator()(_RAIter __first, _RAIter __last,
                  _StrictWeakOrdering __comp)
  { __gnu_sequential::sort(__first, __last, __comp); }
};

/**
 * @brief Sampling based splitting for parallel multiway-merge routine.
 */
template<
    bool __stable
  , typename _RAIterIterator
  , typename _Compare
  , typename _DifferenceType>
void multiway_merge_sampling_splitting(
    _RAIterIterator __seqs_begin,
    _RAIterIterator __seqs_end,
    _DifferenceType __length, _DifferenceType __total_length, _Compare __comp,
    std::vector<std::pair<_DifferenceType, _DifferenceType> > *__pieces)
{
  typedef typename std::iterator_traits<_RAIterIterator>
    ::value_type::first_type
    _RAIter1;
  typedef typename std::iterator_traits<_RAIter1>::value_type
    _ValueType;

  // __k sequences.
  int __k = static_cast<int>(__seqs_end - __seqs_begin);

  int __num_threads = omp_get_num_threads();

  _DifferenceType __num_samples =
      __gnu_parallel::_Settings::get().merge_oversampling * __num_threads;

  _ValueType* __samples = static_cast<_ValueType*>(
    ::operator new(sizeof(_ValueType) * __k * __num_samples));
  // Sample.
  for (int __s = 0; __s < __k; ++__s)
    for (_DifferenceType __i = 0; __i < __num_samples; ++__i)
      {
        _DifferenceType sample_index =
            static_cast<_DifferenceType>(
                _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__s])
                    * (double(__i + 1) / (__num_samples + 1))
                    * (double(__length) / __total_length));
        new(&(__samples[__s * __num_samples + __i]))
            _ValueType(__seqs_begin[__s].first[sample_index]);
      }

  // Sort stable or non-stable, depending on value of template parameter
  // "__stable".
  _SamplingSorter<__stable, _ValueType*, _Compare>()(
      __samples, __samples + (__num_samples * __k), __comp);

  for (int __slab = 0; __slab < __num_threads; ++__slab)
    // For each slab / processor.
    for (int __seq = 0; __seq < __k; ++__seq)
      {
        // For each sequence.
        if (__slab > 0)
          __pieces[__slab][__seq].first =
              std::upper_bound(
                __seqs_begin[__seq].first,
                __seqs_begin[__seq].second,
                __samples[__num_samples * __k * __slab / __num_threads],
                  __comp)
              - __seqs_begin[__seq].first;
        else
          // Absolute beginning.
          __pieces[__slab][__seq].first = 0;
        if ((__slab + 1) < __num_threads)
          __pieces[__slab][__seq].second =
              std::upper_bound(
                  __seqs_begin[__seq].first,
                  __seqs_begin[__seq].second,
                  __samples[__num_samples * __k * (__slab + 1) /
                      __num_threads], __comp)
              - __seqs_begin[__seq].first;
        else
            // Absolute end.
          __pieces[__slab][__seq].second = _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__seq]);
      }
    ::operator delete(__samples);
}

/**
 * @brief Exact splitting for parallel multiway-merge routine.
 *
 * None of the passed sequences may be empty.
 */
template<
    bool __stable
  , typename _RAIterIterator
  , typename _Compare
  , typename _DifferenceType>
void multiway_merge_exact_splitting(
    _RAIterIterator __seqs_begin,
    _RAIterIterator __seqs_end,
    _DifferenceType __length, _DifferenceType __total_length, _Compare __comp,
    std::vector<std::pair<_DifferenceType, _DifferenceType> > *__pieces)
{
  typedef typename std::iterator_traits<_RAIterIterator>
    ::value_type::first_type
    _RAIter1;

  const bool __tight = (__total_length == __length);

  // __k sequences.
  const int __k = static_cast<int>(__seqs_end - __seqs_begin);

  const int __num_threads = omp_get_num_threads();

  // (Settings::multiway_merge_splitting == __gnu_parallel::_Settings::EXACT).
  std::vector<_RAIter1>* __offsets =
      new std::vector<_RAIter1>[__num_threads];
  std::vector<
      std::pair<_RAIter1, _RAIter1>
      > __se(__k);

  copy(__seqs_begin, __seqs_end, __se.begin());

  _DifferenceType* __borders =
      new _DifferenceType[__num_threads + 1];
  equally_split(__length, __num_threads, __borders);

  for (int __s = 0; __s < (__num_threads - 1); ++__s)
    {
      __offsets[__s].resize(__k);
      multiseq_partition(
          __se.begin(), __se.end(), __borders[__s + 1],
          __offsets[__s].begin(), __comp);

      // Last one also needed and available.
      if (!__tight)
        {
          __offsets[__num_threads - 1].resize(__k);
          multiseq_partition(__se.begin(), __se.end(),
                _DifferenceType(__length),
                __offsets[__num_threads - 1].begin(),  __comp);
        }
    }
  delete[] __borders;

  for (int __slab = 0; __slab < __num_threads; ++__slab)
    {
      // For each slab / processor.
      for (int __seq = 0; __seq < __k; ++__seq)
        {
          // For each sequence.
          if (__slab == 0)
            {
              // Absolute beginning.
              __pieces[__slab][__seq].first = 0;
            }
          else
            __pieces[__slab][__seq].first =
                __pieces[__slab - 1][__seq].second;
          if (!__tight || __slab < (__num_threads - 1))
            __pieces[__slab][__seq].second =
                __offsets[__slab][__seq] - __seqs_begin[__seq].first;
          else
            {
              // __slab == __num_threads - 1
              __pieces[__slab][__seq].second =
                  _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__seq]);
            }
        }
    }
  delete[] __offsets;
}

/** @brief Parallel multi-way merge routine.
 *
 * The _GLIBCXX_PARALLEL_DECISION is based on the branching factor
 * and runtime settings.
 *
 * Must not be called if the number of sequences is 1.
 *
 * @param Splitter functor to split input (either __exact or sampling based)
 *
 * @param __seqs_begin Begin iterator of iterator pair input sequence.
 * @param __seqs_end End iterator of iterator pair input sequence.
 * @param __target Begin iterator of __output sequence.
 * @param __comp Comparator.
 * @param __length Maximum length to merge, possibly larger than the
 * number of elements available.
 * @param __stable Stable merging incurs __a performance penalty.
 * @param __sentinel Ignored.
 * @return End iterator of output sequence.
 */
template<
    bool __stable,
    bool __sentinels,
    typename _RAIterIterator,
    typename _RAIter3,
    typename _DifferenceTp,
    typename Splitter,
    typename _Compare
    >
  _RAIter3
  parallel_multiway_merge(_RAIterIterator __seqs_begin,
                          _RAIterIterator __seqs_end,
                          _RAIter3 __target,
                          Splitter splitter,
                          _DifferenceTp __length,
                          _Compare __comp,
                          _ThreadIndex __num_threads)
    {
#if _GLIBCXX_ASSERTIONS
      _GLIBCXX_PARALLEL_ASSERT(__seqs_end - __seqs_begin > 1);
#endif

      _GLIBCXX_CALL(__length)

      typedef _DifferenceTp _DifferenceType;
      typedef typename std::iterator_traits<_RAIterIterator>
        ::value_type::first_type
        _RAIter1;
      typedef typename
        std::iterator_traits<_RAIter1>::value_type _ValueType;

      // Leave only non-empty sequences.
      typedef std::pair<_RAIter1, _RAIter1> seq_type;
      seq_type* __ne_seqs = new seq_type[__seqs_end - __seqs_begin];
      int __k = 0;
      _DifferenceType __total_length = 0;
      for (_RAIterIterator __raii = __seqs_begin;
           __raii != __seqs_end; ++__raii)
        {
          _DifferenceTp __seq_length = _GLIBCXX_PARALLEL_LENGTH(*__raii);
          if(__seq_length > 0)
            {
              __total_length += __seq_length;
              __ne_seqs[__k++] = *__raii;
            }
        }

      _GLIBCXX_CALL(__total_length)

      __length = std::min<_DifferenceTp>(__length, __total_length);

      if (__total_length == 0 || __k == 0)
      {
        delete[] __ne_seqs;
        return __target;
      }

      std::vector<std::pair<_DifferenceType, _DifferenceType> >* __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 (int __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 (int __c = 0; __c < __k; ++__c)
            __target_position += __pieces[__iam][__c].first;

          seq_type* __chunks = new seq_type[__k];

          for (int __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:
 *
 * <pre>
 *   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<std::pair<int*> > seqs;
 *   for (int __i = 0; __i < 10; ++__i)
 *     { seqs.push(std::make_pair<int*>(sequences[__i], sequences[__i] + 10)) }
 *
 *   multiway_merge(seqs.begin(), seqs.end(), __target, std::less<int>(), 33);
 * </pre>
 *
 * @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).
 *
 * @param _RAIterPairIterator iterator over sequence
 *    of pairs of iterators
 * @param _RAIterOut iterator over target sequence
 * @param _DifferenceTp difference type for the sequence
 * @param _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<
    typename _RAIterPairIterator
  , typename _RAIterOut
  , typename _DifferenceTp
  , typename _Compare>
_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
    </* __stable = */ false, /* __sentinels = */ false>
      (__seqs_begin, __seqs_end, __target, *(__seqs_begin->second), __length, __comp);
}

// public interface
template<
    typename _RAIterPairIterator
  , typename _RAIterOut
  , typename _DifferenceTp
  , typename _Compare>
_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
                    </* __stable = */ false, /* __sentinels = */ false>(
          __seqs_begin, __seqs_end, __target,
          multiway_merge_exact_splitting</* __stable = */ false,
            typename std::iterator_traits<_RAIterPairIterator>
              ::value_type*, _Compare, _DifferenceTp>,
          static_cast<_DifferenceType>(__length), __comp, __tag.__get_num_threads());
    else
      return __sequential_multiway_merge
                      </* __stable = */ false, /* __sentinels = */ false>(
          __seqs_begin, __seqs_end, __target, *(__seqs_begin->second), __length, __comp);
}

// public interface
template<
    typename _RAIterPairIterator
  , typename _RAIterOut
  , typename _DifferenceTp
  , typename _Compare>
_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
                    </* __stable = */ false, /* __sentinels = */ false>(
          __seqs_begin, __seqs_end,
          __target,
          multiway_merge_exact_splitting</* __stable = */ false,
            typename std::iterator_traits<_RAIterPairIterator>
              ::value_type*, _Compare, _DifferenceTp>,
          static_cast<_DifferenceType>(__length), __comp, __tag.__get_num_threads());
    else
      return __sequential_multiway_merge
                      </* __stable = */ false, /* __sentinels = */ false>(
          __seqs_begin, __seqs_end,
          __target, *(__seqs_begin->second), __length, __comp);
}

// public interface
template<
    typename _RAIterPairIterator
  , typename _RAIterOut
  , typename _DifferenceTp
  , typename _Compare>
_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<
    typename _RAIterPairIterator
  , typename _RAIterOut
  , typename _DifferenceTp
  , typename _Compare>
_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<
    typename _RAIterPairIterator
  , typename _RAIterOut
  , typename _DifferenceTp
  , typename _Compare>
_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
      </* __stable = */ true, /* __sentinels = */ false>
        (__seqs_begin, __seqs_end, __target, *(__seqs_begin->second), __length, __comp);
}

// public interface
template<
    typename _RAIterPairIterator
  , typename _RAIterOut
  , typename _DifferenceTp
  , typename _Compare>
_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
        </* __stable = */ true, /* __sentinels = */ false>(
          __seqs_begin, __seqs_end,
          __target,
          multiway_merge_exact_splitting</* __stable = */ true,
            typename std::iterator_traits<_RAIterPairIterator>
              ::value_type*, _Compare, _DifferenceTp>,
          static_cast<_DifferenceType>(__length), __comp, __tag.__get_num_threads());
    else
      return __sequential_multiway_merge</* __stable = */ true,
        /* __sentinels = */ false>(
          __seqs_begin, __seqs_end,
          __target, *(__seqs_begin->second), __length, __comp);
}

// public interface
template<
    typename _RAIterPairIterator
  , typename _RAIterOut
  , typename _DifferenceTp
  , typename _Compare>
_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
        </* __stable = */ true, /* __sentinels = */ false>(
          __seqs_begin, __seqs_end,
          __target,
          multiway_merge_sampling_splitting</* __stable = */ true,
            typename std::iterator_traits<_RAIterPairIterator>
              ::value_type*, _Compare, _DifferenceTp>,
          static_cast<_DifferenceType>(__length), __comp, __tag.__get_num_threads());
    else
      return __sequential_multiway_merge
        </* __stable = */ true, /* __sentinels = */ false>(
          __seqs_begin, __seqs_end,
          __target, *(__seqs_begin->second), __length, __comp);
}


// public interface
template<
    typename _RAIterPairIterator
  , typename _RAIterOut
  , typename _DifferenceTp
  , typename _Compare>
_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<
    typename _RAIterPairIterator
  , typename _RAIterOut
  , typename _DifferenceTp
  , typename _Compare>
_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:
 *
 * <pre>
 *   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<std::pair<int*> > seqs;
 *   for (int __i = 0; __i < 10; ++__i)
 *     { seqs.push(std::make_pair<int*>(sequences[__i], sequences[__i] + 10)) }
 *
 *   multiway_merge(seqs.begin(), seqs.end(), __target, std::less<int>(), 33);
 * </pre>
 *
 * @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
 *
 * @param _RAIterPairIterator iterator over sequence
 *    of pairs of iterators
 * @param _RAIterOut iterator over target sequence
 * @param _DifferenceTp difference type for the sequence
 * @param _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<
    typename _RAIterPairIterator
  , typename _RAIterOut
  , typename _DifferenceTp
  , typename _Compare>
_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
      </* __stable = */ false, /* __sentinels = */ true>
        (__seqs_begin, __seqs_end,
         __target, *(__seqs_begin->second), __length, __comp);
}

// public interface
template<
    typename _RAIterPairIterator
  , typename _RAIterOut
  , typename _DifferenceTp
  , typename _Compare>
_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
        </* __stable = */ false, /* __sentinels = */ true>(
          __seqs_begin, __seqs_end,
          __target,
          multiway_merge_exact_splitting</* __stable = */ false,
            typename std::iterator_traits<_RAIterPairIterator>
              ::value_type*, _Compare, _DifferenceTp>,
          static_cast<_DifferenceType>(__length), __comp, __tag.__get_num_threads());
    else
      return __sequential_multiway_merge
        </* __stable = */ false, /* __sentinels = */ true>(
          __seqs_begin, __seqs_end,
          __target, *(__seqs_begin->second), __length, __comp);
}

// public interface
template<
    typename _RAIterPairIterator
  , typename _RAIterOut
  , typename _DifferenceTp
  , typename _Compare>
_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
        </* __stable = */ false, /* __sentinels = */ true>
          (__seqs_begin, __seqs_end, __target,
          multiway_merge_sampling_splitting</* __stable = */ false,
            typename std::iterator_traits<_RAIterPairIterator>
              ::value_type*, _Compare, _DifferenceTp>,
          static_cast<_DifferenceType>(__length), __comp, __tag.__get_num_threads());
    else
      return __sequential_multiway_merge
        </* __stable = */false, /* __sentinels = */ true>(
          __seqs_begin, __seqs_end,
          __target, *(__seqs_begin->second), __length, __comp);
}

// public interface
template<
    typename _RAIterPairIterator
  , typename _RAIterOut
  , typename _DifferenceTp
  , typename _Compare>
_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<
    typename _RAIterPairIterator
  , typename _RAIterOut
  , typename _DifferenceTp
  , typename _Compare>
_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<
    typename _RAIterPairIterator
  , typename _RAIterOut
  , typename _DifferenceTp
  , typename _Compare>
_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
      </* __stable = */ true, /* __sentinels = */ true>
        (__seqs_begin, __seqs_end, __target, *(__seqs_begin->second), __length, __comp);
}

// public interface
template<
    typename _RAIterPairIterator
  , typename _RAIterOut
  , typename _DifferenceTp
  , typename _Compare>
_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
        </* __stable = */ true, /* __sentinels = */ true>(
          __seqs_begin, __seqs_end,
          __target,
          multiway_merge_exact_splitting</* __stable = */ true,
            typename std::iterator_traits<_RAIterPairIterator>
              ::value_type*, _Compare, _DifferenceTp>,
          static_cast<_DifferenceType>(__length), __comp, __tag.__get_num_threads());
    else
      return __sequential_multiway_merge
        </* __stable = */ true, /* __sentinels = */ true>(
          __seqs_begin, __seqs_end, __target, *(__seqs_begin->second), __length, __comp);
}

// public interface
template<
    typename _RAIterPairIterator
  , typename _RAIterOut
  , typename _DifferenceTp
  , typename _Compare>
_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
        </* __stable = */ true, /* __sentinels = */ true>(
          __seqs_begin, __seqs_end,
          __target,
          multiway_merge_sampling_splitting</* __stable = */ true,
            typename std::iterator_traits<_RAIterPairIterator>
              ::value_type*, _Compare, _DifferenceTp>,
          static_cast<_DifferenceType>(__length), __comp, __tag.__get_num_threads());
    else
      return __sequential_multiway_merge
        </* __stable = */ true, /* __sentinels = */ true>(
          __seqs_begin, __seqs_end,
          __target, *(__seqs_begin->second), __length, __comp);
}

// public interface
template<
    typename _RAIterPairIterator
  , typename _RAIterOut
  , typename _DifferenceTp
  , typename _Compare>
_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<
    typename _RAIterPairIterator
  , typename _RAIterOut
  , typename _DifferenceTp
  , typename _Compare>
_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 */