multiway_merge.h

Go to the documentation of this file.

// -*- C++ -*-

// Copyright (C) 2007-2018 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>
#include <parallel/multiseq_selection.h>
#if _GLIBCXX_PARALLEL_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
{
  template<typename _RAIter1, typename _RAIter2, typename _OutputIterator,
           typename _DifferenceTp, typename _Compare>
    _OutputIterator
    __merge_advance(_RAIter1&, _RAIter1, _RAIter2&, _RAIter2,
                    _OutputIterator, _DifferenceTp, _Compare);

  /** @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 __end End iterator of sequence.
      *  @param __comp Comparator provided for associated overloaded
      *  compare operators. */
      _GuardedIterator(_RAIter __begin, _RAIter __end, _Compare& __comp)
      : _M_current(__begin), _M_end(__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; }

      /** @brief Compare two elements referenced by guarded iterators.
       *  @param __bi1 First iterator.
       *  @param __bi2 Second iterator.
       *  @return @c true if less. */
      friend 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. */
      friend 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 _UnguardedIterator
    {
    private:
      /** @brief Current iterator __position. */
      _RAIter _M_current;
      /** @brief _Compare. */
      _Compare& __comp;

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

      /** @brief Pre-increment operator.
      *  @return This. */
      _UnguardedIterator<_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; }

      /** @brief Compare two elements referenced by unguarded iterators.
       *  @param __bi1 First iterator.
       *  @param __bi2 Second iterator.
       *  @return @c true if less. */
      friend bool
      operator<(_UnguardedIterator<_RAIter, _Compare>& __bi1,
                _UnguardedIterator<_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. */
      friend bool
      operator<=(_UnguardedIterator<_RAIter, _Compare>& __bi1,
                 _UnguardedIterator<_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 @a not 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_PARALLEL_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_PARALLEL_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 @a not 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>
        ::difference_type _SeqNumber;
      typedef typename std::iterator_traits<_RAIterIterator>
        ::value_type::first_type
        _RAIter1;
      typedef typename std::iterator_traits<_RAIter1>::value_type
        _ValueType;

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

      _LT __lt(__k, __comp);

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

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

      for (_SeqNumber __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();

      _SeqNumber __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>
        ::difference_type _SeqNumber;
      typedef typename std::iterator_traits<_RAIterIterator>
        ::value_type::first_type
        _RAIter1;
      typedef typename std::iterator_traits<_RAIter1>::value_type
        _ValueType;

      _SeqNumber __k = __seqs_end - __seqs_begin;

      _LT __lt(__k, __sentinel, __comp);

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

      __lt.__init();

      _SeqNumber __source;

#if _GLIBCXX_PARALLEL_ASSERTIONS
      _DifferenceType __i = 0;
#endif

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

#if _GLIBCXX_PARALLEL_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_PARALLEL_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.
   *
   * @tparam UnguardedLoserTree _Loser Tree variant to use for the unguarded
   *   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 sequence ends to the sentinel.  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_PARALLEL_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 he 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<_UnguardedIterator>
          (__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<_UnguardedIterator>
          (__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 __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>
        ::difference_type _SeqNumber;
      typedef typename std::iterator_traits<_RAIterIterator>
        ::value_type::first_type
        _RAIter1;
      typedef typename std::iterator_traits<_RAIter1>::value_type
        _ValueType;

#if _GLIBCXX_PARALLEL_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;
      _SeqNumber __k = static_cast<_SeqNumber>(__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_PARALLEL_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>
        ::difference_type _SeqNumber;
      typedef typename std::iterator_traits<_RAIterIterator>
        ::value_type::first_type
        _RAIter1;
      typedef typename std::iterator_traits<_RAIter1>::value_type
        _ValueType;

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

      const _ThreadIndex __num_threads = omp_get_num_threads();

      const _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 (_SeqNumber __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 (_ThreadIndex __slab = 0; __slab < __num_threads; ++__slab)
        // For each slab / processor.
        for (_SeqNumber __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]);
          }

      for (_SeqNumber __s = 0; __s < __k; ++__s)
        for (_DifferenceType __i = 0; __i < __num_samples; ++__i)
          __samples[__s * __num_samples + __i].~_ValueType();
      ::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>
        ::difference_type _SeqNumber;
      typedef typename std::iterator_traits<_RAIterIterator>
        ::value_type::first_type
        _RAIter1;

      const bool __tight = (__total_length == __length);

      // __k sequences.
      const _SeqNumber __k = __seqs_end - __seqs_begin;

      const _ThreadIndex __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 (_ThreadIndex __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 (_ThreadIndex __slab = 0; __slab < __num_threads; ++__slab)
        {
          // For each slab / processor.
          for (_SeqNumber __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.
   *
   * @tparam _Splitter functor to split input (either __exact or sampling based)
   * @tparam __stable Stable merging incurs a performance penalty.
   * @tparam __sentinel Ignored.
   *
   * @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.
   * @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_PARALLEL_ASSERTIONS
        _GLIBCXX_PARALLEL_ASSERT(__seqs_end - __seqs_begin > 1);
#endif

        _GLIBCXX_CALL(__length)

        typedef _DifferenceTp _DifferenceType;
        typedef typename std::iterator_traits<_RAIterIterator>
          ::difference_type _SeqNumber;
        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];
        _SeqNumber __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 (_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_PARALLEL_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).
   *
   * @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<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
   *
   * @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<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 */