diff --git a/libcxx/include/__algorithm/sort.h b/libcxx/include/__algorithm/sort.h
--- a/libcxx/include/__algorithm/sort.h
+++ b/libcxx/include/__algorithm/sort.h
@@ -123,6 +123,86 @@
     return __r;
 }
 
+// Ensures that __c(*__x, *__y) is true by swapping *__x and *__y if necessary.
+template <typename _Compare, typename _RandomAccessIterator>
+inline _LIBCPP_HIDDEN void __cond_swap(_RandomAccessIterator __x, _RandomAccessIterator __y, _Compare __c) {
+  using value_type = typename iterator_traits<_RandomAccessIterator>::value_type;
+  bool __r = __c(*__x, *__y);
+  value_type __tmp = __r ? *__x : *__y;
+  *__y = __r ? *__y : *__x;
+  *__x = __tmp;
+}
+
+// Ensures that *__x, *__y and *__z are ordered according to the comparator __c,
+// under the assumption that *__y and *__z are already ordered.
+template <typename _Compare, typename _RandomAccessIterator>
+inline _LIBCPP_HIDDEN void __partially_sorted_swap(_RandomAccessIterator __x, _RandomAccessIterator __y,
+                                                   _RandomAccessIterator __z, _Compare __c) {
+  using value_type = typename iterator_traits<_RandomAccessIterator>::value_type;
+  bool __r = __c(*__z, *__x);
+  value_type __tmp = __r ? *__z : *__x;
+  *__z = __r ? *__x : *__z;
+  __r = __c(__tmp, *__y);
+  *__x = __r ? *__x : *__y;
+  *__y = __r ? *__y : __tmp;
+}
+
+template <typename _Compare, typename _RandomAccessIterator>
+inline _LIBCPP_HIDDEN
+    __enable_if_t<_VSTD::is_integral< typename iterator_traits<_RandomAccessIterator>::value_type>::value, void>
+    __sort3_internal(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3, _Compare __c) {
+  _VSTD::__cond_swap(__x2, __x3, __c);
+  _VSTD::__partially_sorted_swap(__x1, __x2, __x3, __c);
+}
+
+template <typename _Compare, typename _RandomAccessIterator>
+inline _LIBCPP_HIDDEN
+    __enable_if_t<!_VSTD::is_integral< typename iterator_traits<_RandomAccessIterator>::value_type>::value, void>
+    __sort3_internal(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3, _Compare __c) {
+  _VSTD::__sort3<_Compare>(__x1, __x2, __x3, __c);
+}
+
+template <typename _Compare, typename _RandomAccessIterator>
+inline _LIBCPP_HIDDEN
+    __enable_if_t<_VSTD::is_integral< typename iterator_traits<_RandomAccessIterator>::value_type>::value, void>
+    __sort4_internal(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3,
+                     _RandomAccessIterator __x4, _Compare __c) {
+  _VSTD::__cond_swap(__x1, __x3, __c);
+  _VSTD::__cond_swap(__x2, __x4, __c);
+  _VSTD::__cond_swap(__x1, __x2, __c);
+  _VSTD::__cond_swap(__x3, __x4, __c);
+  _VSTD::__cond_swap(__x2, __x3, __c);
+}
+
+template <typename _Compare, typename _RandomAccessIterator>
+inline _LIBCPP_HIDDEN
+    __enable_if_t<!_VSTD::is_integral< typename iterator_traits<_RandomAccessIterator>::value_type>::value, void>
+    __sort4_internal(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3,
+                     _RandomAccessIterator __x4, _Compare __c) {
+  _VSTD::__sort4(__x1, __x2, __x3, __x4, __c);
+}
+
+template <typename _Compare, typename _RandomAccessIterator>
+inline _LIBCPP_HIDDEN
+    __enable_if_t<_VSTD::is_integral< typename iterator_traits<_RandomAccessIterator>::value_type>::value, void>
+    __sort5_internal(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3,
+                     _RandomAccessIterator __x4, _RandomAccessIterator __x5, _Compare __c) {
+  _VSTD::__cond_swap(__x1, __x2, __c);
+  _VSTD::__cond_swap(__x4, __x5, __c);
+  _VSTD::__partially_sorted_swap(__x3, __x4, __x5, __c);
+  _VSTD::__cond_swap(__x2, __x5, __c);
+  _VSTD::__partially_sorted_swap(__x1, __x3, __x4, __c);
+  _VSTD::__partially_sorted_swap(__x2, __x3, __x4, __c);
+}
+
+template <typename _Compare, typename _RandomAccessIterator>
+inline _LIBCPP_HIDDEN
+    __enable_if_t<!_VSTD::is_integral< typename iterator_traits<_RandomAccessIterator>::value_type>::value, void>
+    __sort5_internal(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3,
+                     _RandomAccessIterator __x4, _RandomAccessIterator __x5, _Compare __c) {
+  _VSTD::__sort5(__x1, __x2, __x3, __x4, __x5, __c);
+}
+
 // Assumes size > 0
 template <class _Compare, class _BidirectionalIterator>
 _LIBCPP_CONSTEXPR_AFTER_CXX11 void
@@ -163,7 +243,7 @@
     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
     _RandomAccessIterator __j = __first+difference_type(2);
-    _VSTD::__sort3<_Compare>(__first, __first+difference_type(1), __j, __comp);
+    _VSTD::__sort3_internal<_Compare>(__first, __first + difference_type(1), __j, __comp);
     for (_RandomAccessIterator __i = __j+difference_type(1); __i != __last; ++__i)
     {
         if (__comp(*__i, *__j))
@@ -197,18 +277,20 @@
             swap(*__first, *__last);
         return true;
     case 3:
-        _VSTD::__sort3<_Compare>(__first, __first+difference_type(1), --__last, __comp);
-        return true;
+      _VSTD::__sort3_internal<_Compare>(__first, __first + difference_type(1), --__last, __comp);
+      return true;
     case 4:
-        _VSTD::__sort4<_Compare>(__first, __first+difference_type(1), __first+difference_type(2), --__last, __comp);
-        return true;
+      _VSTD::__sort4_internal<_Compare>(__first, __first + difference_type(1), __first + difference_type(2), --__last,
+                                        __comp);
+      return true;
     case 5:
-        _VSTD::__sort5<_Compare>(__first, __first+difference_type(1), __first+difference_type(2), __first+difference_type(3), --__last, __comp);
-        return true;
+      _VSTD::__sort5_internal<_Compare>(__first, __first + difference_type(1), __first + difference_type(2),
+                                        __first + difference_type(3), --__last, __comp);
+      return true;
     }
     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
     _RandomAccessIterator __j = __first+difference_type(2);
-    _VSTD::__sort3<_Compare>(__first, __first+difference_type(1), __j, __comp);
+    _VSTD::__sort3_internal<_Compare>(__first, __first + difference_type(1), __j, __comp);
     const unsigned __limit = 8;
     unsigned __count = 0;
     for (_RandomAccessIterator __i = __j+difference_type(1); __i != __last; ++__i)
@@ -290,14 +372,16 @@
                 swap(*__first, *__last);
             return;
         case 3:
-            _VSTD::__sort3<_Compare>(__first, __first+difference_type(1), --__last, __comp);
-            return;
+          _VSTD::__sort3_internal<_Compare>(__first, __first + difference_type(1), --__last, __comp);
+          return;
         case 4:
-            _VSTD::__sort4<_Compare>(__first, __first+difference_type(1), __first+difference_type(2), --__last, __comp);
-            return;
+          _VSTD::__sort4_internal<_Compare>(__first, __first + difference_type(1), __first + difference_type(2),
+                                            --__last, __comp);
+          return;
         case 5:
-            _VSTD::__sort5<_Compare>(__first, __first+difference_type(1), __first+difference_type(2), __first+difference_type(3), --__last, __comp);
-            return;
+          _VSTD::__sort5_internal<_Compare>(__first, __first + difference_type(1), __first + difference_type(2),
+                                            __first + difference_type(3), --__last, __comp);
+          return;
         }
         if (__len <= __limit)
         {