merge from trunkprofile-stdlib

git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/branches/profile-stdlib@154052 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 1848 insertions, 1963 deletions

diff --git a/libstdc++-v3/include/parallel/multiway_merge.h b/libstdc++-v3/include/parallel/multiway_merge.h
index 310a07a766c..cdf21540d12 100644
--- a/libstdc++-v3/include/parallel/multiway_merge.h
+++ b/libstdc++-v3/include/parallel/multiway_merge.h
@@ -54,2113 +54,1998 @@
 
 namespace __gnu_parallel
 {
+  /** @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;
+      }
 
-// 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++()
+      /** @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
     {
-      ++_M_current;
-      return *this;
-    }
+    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 __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; }
-
-    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 _UnguardedIterator;
-
-template<typename _RAIter, typename _Compare>
-  inline bool
-  operator<(_UnguardedIterator<_RAIter, _Compare>& __bi1,
-            _UnguardedIterator<_RAIter, _Compare>& __bi2);
-
-template<typename _RAIter, typename _Compare>
-  inline bool
-  operator<=(_UnguardedIterator<_RAIter, _Compare>& __bi1,
-             _UnguardedIterator<_RAIter, _Compare>& __bi2);
-
-template<typename _RAIter, typename _Compare>
-  class _UnguardedIterator
-  {
-  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. */
-    _UnguardedIterator(_RAIter __begin,
-                       _RAIter _M_end, _Compare& __comp)
-    : _M_current(__begin), __comp(__comp)
-    { }
-
-    /** @brief Pre-increment operator.
-    *  @return This. */
-    _UnguardedIterator<_RAIter, _Compare>&
-    operator++()
+      /** @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 <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)
     {
-      ++_M_current;
-      return *this;
-    }
+      _GLIBCXX_CALL(__length);
 
-    /** @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>(
-      _UnguardedIterator<_RAIter, _Compare>& __bi1,
-      _UnguardedIterator<_RAIter, _Compare>& __bi2);
-
-    friend bool
-    operator<= <_RAIter, _Compare>(
-      _UnguardedIterator<_RAIter, _Compare>& __bi1,
-      _UnguardedIterator<_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<(_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. */
-template<typename _RAIter, typename _Compare>
-  inline 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 <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;
+      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;
+      _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);
+      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;
+      if (__seq0 <= __seq1)
+	{
+          if (__seq1 <= __seq2)
+            goto __s012;
           else
-            goto __s021;
-      }
-    else
-      {
-        if (__seq1 <= __seq2)
-          {
-            if (__seq0 <= __seq2)
-              goto __s102;
+            if (__seq2 <  __seq0)
+              goto __s201;
             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, < , < );
+              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:
-    ;
+    __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);
+    _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)
-            }
+      __seqs_begin[0].first = __seq0;
+      __seqs_begin[1].first = __seq1;
+      __seqs_begin[2].first = __seq2;
 
-#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, < , < , < );
+      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)
+    __finish:
+      ;
 
-    typedef _DifferenceTp _DifferenceType;
-    typedef typename std::iterator_traits<_RAIterIterator>
-      ::value_type::first_type
-      _RAIter1;
-    typedef typename std::iterator_traits<_RAIter1>::value_type
-      _ValueType;
+      __seqs_begin[0].first = __seq0;
+      __seqs_begin[1].first = __seq1;
+      __seqs_begin[2].first = __seq2;
+      __seqs_begin[3].first = __seq3;
 
-    int __k = static_cast<int>(__seqs_end - __seqs_begin);
+      return __target;
+    }
 
-    LT __lt(__k, __comp);
+  /** @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)
 
-    // Default value for potentially non-default-constructible types.
-    _ValueType* __arbitrary_element = NULL;
+      typedef _DifferenceTp _DifferenceType;
+      typedef typename std::iterator_traits<_RAIterIterator>
+	::value_type::first_type
+	_RAIter1;
+      typedef typename std::iterator_traits<_RAIter1>::value_type
+	_ValueType;
 
-    for (int __t = 0; __t < __k; ++__t)
-      {
-        if(__arbitrary_element == NULL
-            && _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__t]) > 0)
-          __arbitrary_element = &(*__seqs_begin[__t].first);
-      }
+      int __k = static_cast<int>(__seqs_end - __seqs_begin);
 
-    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 __lt(__k, __comp);
 
-    __lt.__init();
+      // Default value for potentially non-default-constructible types.
+      _ValueType* __arbitrary_element = NULL;
 
-    int __source;
+      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 (_DifferenceType __i = 0; __i < __length; ++__i)
-      {
-        //take out
-        __source = __lt.__get_min_source();
+      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);
+	}
 
-        *(__target++) = *(__seqs_begin[__source].first++);
+      __lt.__init();
 
-        // 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);
-      }
+      int __source;
 
-    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;
+      for (_DifferenceType __i = 0; __i < __length; ++__i)
+	{
+          //take out
+          __source = __lt.__get_min_source();
 
-    typedef typename std::iterator_traits<_RAIterIterator>
-      ::value_type::first_type
-      _RAIter1;
-    typedef typename std::iterator_traits<_RAIter1>::value_type
-      _ValueType;
+          *(__target++) = *(__seqs_begin[__source].first++);
 
-    int __k = __seqs_end - __seqs_begin;
+          // 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);
+	}
 
-    LT __lt(__k, __sentinel, __comp);
+      return __target;
+    }
 
-    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);
-      }
+  /** @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;
 
-    __lt.__init();
+      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;
 
-    int __source;
+      _LT __lt(__k, __sentinel, __comp);
 
+      for (int __t = 0; __t < __k; ++__t)
+	{
 #if _GLIBCXX_ASSERTIONS
-    _DifferenceType __i = 0;
+          _GLIBCXX_PARALLEL_ASSERT(__seqs_begin[__t].first
+                                   != __seqs_begin[__t].second);
 #endif
+          __lt.__insert_start(*__seqs_begin[__t].first, __t, false);
+	}
 
-    _RAIter3 __target_end = __target + __length;
-    while (__target < __target_end)
-      {
-        // Take out.
-        __source = __lt.__get_min_source();
+      __lt.__init();
+
+      int __source;
 
 #if _GLIBCXX_ASSERTIONS
-        _GLIBCXX_PARALLEL_ASSERT(0 <= __source && __source < __k);
-        _GLIBCXX_PARALLEL_ASSERT(__i == 0
-            || !__comp(*(__seqs_begin[__source].first), *(__target - 1)));
+      _DifferenceType __i = 0;
 #endif
 
-        // Feed.
-        *(__target++) = *(__seqs_begin[__source].first++);
+      _RAIter3 __target_end = __target + __length;
+      while (__target < __target_end)
+	{
+          // Take out.
+          __source = __lt.__get_min_source();
 
 #if _GLIBCXX_ASSERTIONS
-        ++__i;
+          _GLIBCXX_PARALLEL_ASSERT(0 <= __source && __source < __k);
+          _GLIBCXX_PARALLEL_ASSERT(__i == 0
+              || !__comp(*(__seqs_begin[__source].first), *(__target - 1)));
 #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 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);
+          // Feed.
+          *(__target++) = *(__seqs_begin[__source].first++);
 
 #if _GLIBCXX_ASSERTIONS
-    _GLIBCXX_PARALLEL_ASSERT(__target_end == __target + __length);
-    _GLIBCXX_PARALLEL_ASSERT(__is_sorted(__target, __target_end, __comp));
+          ++__i;
 #endif
+          // Replace from same __source.
+          __lt.__delete_min_insert(*__seqs_begin[__source].first, false);
+	}
 
-    // 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.
+      return __target;
+    }
+
+
+  /** @brief Multi-way merging procedure for a high branching factor,
+   *         requiring sentinels to exist.
    *
-   * The default behavior is to use pointers if the data type is four
-   * times as big as the pointer to it.
+   * @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.
    */
-  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,
+  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)
-  {
-    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
+	_RAIterIterator>::value_type::first_type>::value_type&
+				       __sentinel,
+				       _DifferenceTp __length,
+				       _Compare __comp)
+    {
+      _GLIBCXX_CALL(__length)
 
-    _DifferenceTp __total_length = 0;
-    for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s)
-      __total_length += _GLIBCXX_PARALLEL_LENGTH(*__s);
+      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;
 
-    __length = std::min<_DifferenceTp>(__length, __total_length);
+      _RAIter3 __target_end;
 
-    if(__length == 0)
-      return __target;
+      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);
 
-    _RAIter3 __return_target = __target;
-    int __k = static_cast<int>(__seqs_end - __seqs_begin);
+      __target_end = multiway_merge_loser_tree_unguarded<UnguardedLoserTree>
+	(__seqs_begin, __seqs_end, __target, __sentinel, __length, __comp);
 
-    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));
+      _GLIBCXX_PARALLEL_ASSERT(__target_end == __target + __length);
+      _GLIBCXX_PARALLEL_ASSERT(__is_sorted(__target, __target_end, __comp));
 #endif
 
-    return __return_target;
-  }
+      // 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);
 
-/**
- * @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;
+      return __target_end;
+    }
 
-  // __k sequences.
-  int __k = static_cast<int>(__seqs_end - __seqs_begin);
+  /**
+   * @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*));
+    };
 
-  int __num_threads = omp_get_num_threads();
+  /**
+   * @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); }
+    };
 
-  _DifferenceType __num_samples =
-      __gnu_parallel::_Settings::get().merge_oversampling * __num_threads;
+  /**
+   * @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); }
+    };
 
-  _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)
+  /**
+   * @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)
       {
-        _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]);
+	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);
       }
+    };
 
-  // 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)
+  /**
+   * @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)
       {
-        // 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]);
+	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);
       }
-    ::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;
+    };
+
+  /** @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
 
-  const bool __tight = (__total_length == __length);
+      _DifferenceTp __total_length = 0;
+      for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s)
+	__total_length += _GLIBCXX_PARALLEL_LENGTH(*__s);
 
-  // __k sequences.
-  const int __k = static_cast<int>(__seqs_end - __seqs_begin);
+      __length = std::min<_DifferenceTp>(__length, __total_length);
 
-  const int __num_threads = omp_get_num_threads();
+      if(__length == 0)
+	return __target;
 
-  // (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);
+      _RAIter3 __return_target = __target;
+      int __k = static_cast<int>(__seqs_end - __seqs_begin);
 
-  copy(__seqs_begin, __seqs_end, __se.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
 
-  _DifferenceType* __borders =
-      new _DifferenceType[__num_threads + 1];
-  equally_split(__length, __num_threads, __borders);
+      return __return_target;
+    }
 
-  for (int __s = 0; __s < (__num_threads - 1); ++__s)
+  /**
+   * @brief Stable sorting functor.
+   *
+   * Used to reduce code instanciation in multiway_merge_sampling_splitting.
+   */
+  template<bool __stable, class _RAIter, class _StrictWeakOrdering>
+    struct _SamplingSorter
     {
-      __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;
+      void
+      operator()(_RAIter __first, _RAIter __last, _StrictWeakOrdering __comp)
+      { __gnu_sequential::stable_sort(__first, __last, __comp); }
+    };
 
-  for (int __slab = 0; __slab < __num_threads; ++__slab)
+  /**
+   * @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>
     {
-      // 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]);
-            }
-        }
+      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);
     }
-  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)
+
+  /**
+   * @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);
+	_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(__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)
+	_GLIBCXX_CALL(__total_length)
 
-      __length = std::min<_DifferenceTp>(__length, __total_length);
+	__length = std::min<_DifferenceTp>(__length, __total_length);
 
-      if (__total_length == 0 || __k == 0)
-      {
-        delete[] __ne_seqs;
-        return __target;
-      }
+	if (__total_length == 0 || __k == 0)
+	{
+          delete[] __ne_seqs;
+          return __target;
+	}
 
-      std::vector<std::pair<_DifferenceType, _DifferenceType> >* __pieces;
+	std::vector<std::pair<_DifferenceType, _DifferenceType> >* __pieces;
 
-      __num_threads = static_cast<_ThreadIndex>
-        (std::min<_DifferenceType>(__num_threads, __total_length));
+	__num_threads = static_cast<_ThreadIndex>
+          (std::min<_DifferenceType>(__num_threads, __total_length));
 
-#     pragma omp parallel num_threads (__num_threads)
-        {
+#       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);
+	  {
+	    __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;
+	    _DifferenceType __num_samples =
+	      __gnu_parallel::_Settings::get().merge_oversampling
+	      * __num_threads;
 
-              __splitter(__ne_seqs, __ne_seqs + __k, __length, __total_length,
-                       __comp, __pieces);
-            } //single
+	    __splitter(__ne_seqs, __ne_seqs + __k, __length, __total_length,
+		       __comp, __pieces);
+	  } //single
 
-          _ThreadIndex __iam = omp_get_thread_num();
+	  _ThreadIndex __iam = omp_get_thread_num();
 
-          _DifferenceType __target_position = 0;
+	  _DifferenceType __target_position = 0;
 
-          for (int __c = 0; __c < __k; ++__c)
-            __target_position += __pieces[__iam][__c].first;
+	  for (int __c = 0; __c < __k; ++__c)
+	    __target_position += __pieces[__iam][__c].first;
 
-          seq_type* __chunks = new seq_type[__k];
+	  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);
-            }
+	  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);
+	  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
+	  delete[] __chunks;
+	} // parallel
 
 #if _GLIBCXX_ASSERTIONS
-      _GLIBCXX_PARALLEL_ASSERT(
-        __is_sorted(__target, __target + __length, __comp));
+	_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;
-        }
+	__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;
+	delete[] __pieces;
+	delete[] __ne_seqs;
 
-      return __target + __length;
-    }
+	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)
+  /**
+   * @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;
+      // 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
+      // 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::sampling_tag __tag)
-{
-    typedef _DifferenceTp _DifferenceType;
-    _GLIBCXX_CALL(__seqs_end - __seqs_begin)
+	</* __stable = */ false, /* __sentinels = */ false>
+	(__seqs_begin, __seqs_end, __target,
+	 *(__seqs_begin->second), __length, __comp);
+    }
 
-    // catch special case: no sequences
-    if (__seqs_begin == __seqs_end)
-      return __target;
+  // 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);
+    }
 
-    // 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)
+  // 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);
+    }
 
-    // catch special case: no sequences
-    if (__seqs_begin == __seqs_end)
-      return __target;
+  // 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)
 
-    // 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;
 
-    // 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);
+    }
 
-    // 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)
+  // 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);
+    }
 
-    // catch special case: no sequences
-    if (__seqs_begin == __seqs_end)
-      return __target;
+  // 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);
+    }
 
-    // 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)
+  // 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()));
+    }
 
-    // catch special case: no sequences
-    if (__seqs_begin == __seqs_end)
-      return __target;
+  // 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()));
+    }
 
-    // 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)
+  /**
+   * @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;
+      // 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
+      // 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
-    , sampling_tag __tag)
-{
-    typedef _DifferenceTp _DifferenceType;
-    _GLIBCXX_CALL(__seqs_end - __seqs_begin)
+	</* __stable = */ false, /* __sentinels = */ true>
+          (__seqs_begin, __seqs_end,
+           __target, *(__seqs_begin->second), __length, __comp);
+    }
 
-    // catch special case: no sequences
-    if (__seqs_begin == __seqs_end)
-      return __target;
+  // 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);
+    }
 
-    // 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)
+  // 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);
+    }
 
-    // catch special case: no sequences
-    if (__seqs_begin == __seqs_end)
-      return __target;
+  // 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()));
+    }
 
-    // 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)
+  // 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()));
+    }
 
-    // catch special case: no sequences
-    if (__seqs_begin == __seqs_end)
-      return __target;
+  // 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)
 
-    // 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;
 
-    // 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);
+    }
 
-    // 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) >=
+  // 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 >=
+            && ((_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()));
-}
+	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 */