diff --git a/libstdc++-v3/include/bits/list.tcc b/libstdc++-v3/include/bits/list.tcc
index 62b0ba1063a..7f4e1569ab1 100644
--- a/libstdc++-v3/include/bits/list.tcc
+++ b/libstdc++-v3/include/bits/list.tcc
@@ -485,21 +485,34 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
 	  && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
       {
-        list __carry;
-        list __tmp[64];
-        list * __fill = __tmp;
-        list * __counter;
+	using __detail::_Scratch_list;
+	// The algorithm used here is largely unchanged from the SGI STL
+	// and is described in The C++ Standard Template Library by Plauger,
+	// Stepanov, Lee, Musser.
+	// Each element of *this is spliced out and merged into one of the
+	// sorted lists in __tmp, then all the lists in __tmp are merged
+	// together and then swapped back into *this.
+	// Because all nodes end up back in *this we do not need to update
+	// this->size() while nodes are temporarily moved out.
+	_Scratch_list __carry;
+	_Scratch_list __tmp[64];
+	_Scratch_list* __fill = __tmp;
+	_Scratch_list* __counter;
+
+	_Scratch_list::_Ptr_cmp<const_iterator, void> __ptr_comp;
+
 	__try
 	  {
 	    do
 	      {
-		__carry.splice(__carry.begin(), *this, begin());
+		__carry._M_take_one(begin()._M_node);
 
 		for(__counter = __tmp;
 		    __counter != __fill && !__counter->empty();
 		    ++__counter)
 		  {
-		    __counter->merge(__carry);
+
+		    __counter->merge(__carry, __ptr_comp);
 		    __carry.swap(*__counter);
 		  }
 		__carry.swap(*__counter);
@@ -509,14 +522,15 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	    while ( !empty() );
 
 	    for (__counter = __tmp + 1; __counter != __fill; ++__counter)
-	      __counter->merge(*(__counter - 1));
-	    swap( *(__fill - 1) );
+	      __counter->merge(__counter[-1], __ptr_comp);
+	    __fill[-1].swap(this->_M_impl._M_node);
 	  }
 	__catch(...)
 	  {
-	    this->splice(this->end(), __carry);
+	    // Move all nodes back into *this.
+	    __carry._M_put_all(end()._M_node);
 	    for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i)
-	      this->splice(this->end(), __tmp[__i]);
+	      __tmp[__i]._M_put_all(end()._M_node);
 	    __throw_exception_again;
 	  }
       }
@@ -602,42 +616,49 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	// Do nothing if the list has length 0 or 1.
 	if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
 	    && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
-	  {
-	    list __carry;
-	    list __tmp[64];
-	    list * __fill = __tmp;
-	    list * __counter;
-	    __try
-	      {
-		do
-		  {
-		    __carry.splice(__carry.begin(), *this, begin());
+	{
+	  using __detail::_Scratch_list;
+	  _Scratch_list __carry;
+	  _Scratch_list __tmp[64];
+	  _Scratch_list* __fill = __tmp;
+	  _Scratch_list* __counter;
 
-		    for(__counter = __tmp;
-			__counter != __fill && !__counter->empty();
-			++__counter)
-		      {
-			__counter->merge(__carry, __comp);
-			__carry.swap(*__counter);
-		      }
-		    __carry.swap(*__counter);
-		    if (__counter == __fill)
-		      ++__fill;
-		  }
-		while ( !empty() );
+	_Scratch_list::_Ptr_cmp<const_iterator, _StrictWeakOrdering> __ptr_comp
+	  = { __comp };
 
-		for (__counter = __tmp + 1; __counter != __fill; ++__counter)
-		  __counter->merge(*(__counter - 1), __comp);
-		swap(*(__fill - 1));
-	      }
-	    __catch(...)
-	      {
-		this->splice(this->end(), __carry);
-		for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i)
-		  this->splice(this->end(), __tmp[__i]);
-		__throw_exception_again;
-	      }
-	  }
+	  __try
+	    {
+	      do
+		{
+		  __carry._M_take_one(begin()._M_node);
+
+		  for(__counter = __tmp;
+		      __counter != __fill && !__counter->empty();
+		      ++__counter)
+		    {
+
+		      __counter->merge(__carry, __ptr_comp);
+		      __carry.swap(*__counter);
+		    }
+		  __carry.swap(*__counter);
+		  if (__counter == __fill)
+		    ++__fill;
+		}
+	      while ( !empty() );
+
+	      for (__counter = __tmp + 1; __counter != __fill; ++__counter)
+		__counter->merge(__counter[-1], __ptr_comp);
+	      __fill[-1].swap(this->_M_impl._M_node);
+	    }
+	  __catch(...)
+	    {
+	      // Move all nodes back into *this.
+	      __carry._M_put_all(end()._M_node);
+	      for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i)
+		__tmp[__i]._M_put_all(end()._M_node);
+	      __throw_exception_again;
+	    }
+	}
       }
 
 _GLIBCXX_END_NAMESPACE_CONTAINER
diff --git a/libstdc++-v3/include/bits/stl_list.h b/libstdc++-v3/include/bits/stl_list.h
index e11603c0157..81361dfa4d5 100644
--- a/libstdc++-v3/include/bits/stl_list.h
+++ b/libstdc++-v3/include/bits/stl_list.h
@@ -158,6 +158,73 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     private:
       _List_node_base* _M_base() { return this; }
     };
+
+    // Used by list::sort to hold nodes being sorted.
+    struct _Scratch_list : _List_node_base
+    {
+      _Scratch_list() { _M_next = _M_prev = this; }
+
+      bool empty() const { return _M_next == this; }
+
+      void swap(_List_node_base& __l) { _List_node_base::swap(*this, __l); }
+
+      template<typename _Iter, typename _Cmp>
+	struct _Ptr_cmp
+	{
+	  _Cmp _M_cmp;
+
+	  bool
+	  operator()(const __detail::_List_node_base* __lhs,
+		     const __detail::_List_node_base* __rhs) /* not const */
+	  { return _M_cmp(*_Iter(__lhs), *_Iter(__rhs)); }
+	};
+
+      template<typename _Iter>
+	struct _Ptr_cmp<_Iter, void>
+	{
+	  bool
+	  operator()(const __detail::_List_node_base* __lhs,
+		     const __detail::_List_node_base* __rhs) const
+	  { return *_Iter(__lhs) < *_Iter(__rhs); }
+	};
+
+      // Merge nodes from __x into *this. Both lists must be sorted wrt _Cmp.
+      template<typename _Cmp>
+	void
+	merge(_List_node_base& __x, _Cmp __comp)
+	{
+	  _List_node_base* __first1 = _M_next;
+	  _List_node_base* const __last1 = this;
+	  _List_node_base* __first2 = __x._M_next;
+	  _List_node_base* const __last2 = std::__addressof(__x);
+
+	  while (__first1 != __last1 && __first2 != __last2)
+	    {
+	      if (__comp(__first2, __first1))
+		{
+		  _List_node_base* __next = __first2->_M_next;
+		  __first1->_M_transfer(__first2, __next);
+		  __first2 = __next;
+		}
+	      else
+		__first1 = __first1->_M_next;
+	    }
+	  if (__first2 != __last2)
+	    this->_M_transfer(__first2, __last2);
+	}
+
+      // Splice the node at __i into *this.
+      void _M_take_one(_List_node_base* __i)
+      { this->_M_transfer(__i, __i->_M_next); }
+
+      // Splice all nodes from *this after __i.
+      void _M_put_all(_List_node_base* __i)
+      {
+	if (!empty())
+	  __i->_M_transfer(_M_next, this);
+      }
+    };
+
   } // namespace detail
 
 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
diff --git a/libstdc++-v3/src/c++98/list.cc b/libstdc++-v3/src/c++98/list.cc
index 18f0e136c47..c2f5c43622e 100644
--- a/libstdc++-v3/src/c++98/list.cc
+++ b/libstdc++-v3/src/c++98/list.cc
@@ -94,6 +94,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     _M_transfer(_List_node_base * const __first,
 		_List_node_base * const __last) _GLIBCXX_USE_NOEXCEPT
     {
+      __glibcxx_assert(__first != __last);
+
       if (this != __last)
 	{
 	  // Remove [first, last) from its old position.
diff --git a/libstdc++-v3/testsuite/23_containers/list/operations/66742.cc b/libstdc++-v3/testsuite/23_containers/list/operations/66742.cc
new file mode 100644
index 00000000000..24bda3920d8
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/list/operations/66742.cc
@@ -0,0 +1,55 @@
+// { dg-do run { target c++11 } }
+
+#include <list>
+#include <testsuite_allocator.h>
+#include <testsuite_hooks.h>
+
+// PR libstdc++/66742
+// abort on sorting list with custom allocator that is not stateless
+
+template<typename List, typename Cmp = std::less<typename List::value_type>>
+bool is_sorted(const List& l, Cmp cmp = {})
+{
+  auto it = l.begin();
+  auto next = it;
+  const auto end = l.end();
+  if (it == end)
+    return true;
+  while (++next != end)
+    if (cmp(*next, *it))
+      return false;
+    else
+      it = next;
+  return true;
+}
+
+void
+test01()
+{
+  using Alloc = __gnu_test::uneq_allocator<int>;
+  Alloc a1(1);
+  std::list<int, Alloc> l(a1);
+  for (int i = 0; i < 1000; ++i)
+  {
+    l.push_front(i);
+    l.push_back(i + (i % 3));
+  }
+  const auto orig = l;
+
+  l.sort();
+  VERIFY( is_sorted(l) );
+  l.sort();
+  VERIFY( is_sorted(l) );
+
+  l = orig;
+  l.sort(std::less<int>());
+  VERIFY( is_sorted(l) );
+  l.sort(std::greater<int>());
+  VERIFY( is_sorted(l, std::greater<int>()) );
+}
+
+int
+main()
+{
+  test01();
+}
