diff --git a/libcxx/benchmarks/algorithms.bench.cpp b/libcxx/benchmarks/algorithms.bench.cpp
--- a/libcxx/benchmarks/algorithms.bench.cpp
+++ b/libcxx/benchmarks/algorithms.bench.cpp
@@ -14,11 +14,10 @@
 
 namespace {
 
-enum class ValueType { Uint32, Uint64, Pair, Tuple, String };
-struct AllValueTypes : EnumValuesAsTuple<AllValueTypes, ValueType, 5> {
-  static constexpr const char* Names[] = {
-      "uint32", "uint64", "pair<uint32, uint32>",
-      "tuple<uint32, uint64, uint32>", "string"};
+enum class ValueType { Uint32, Uint64, Pair, Tuple, String, Float };
+struct AllValueTypes : EnumValuesAsTuple<AllValueTypes, ValueType, 6> {
+  static constexpr const char* Names[] = {"uint32", "uint64", "pair<uint32, uint32>", "tuple<uint32, uint64, uint32>",
+                                          "string", "float"};
 };
 
 template <class V>
@@ -28,9 +27,8 @@
         V() == ValueType::Uint64, uint64_t,
         std::conditional_t<
             V() == ValueType::Pair, std::pair<uint32_t, uint32_t>,
-            std::conditional_t<V() == ValueType::Tuple,
-                               std::tuple<uint32_t, uint64_t, uint32_t>,
-                               std::string> > > >;
+            std::conditional_t<V() == ValueType::Tuple, std::tuple<uint32_t, uint64_t, uint32_t>,
+                               std::conditional_t< V() == ValueType::String, std::string, float> > > > >;
 
 enum class Order {
   Random,
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<is_arithmetic<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<!is_arithmetic<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<is_arithmetic<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<!is_arithmetic<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<is_arithmetic<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<!is_arithmetic<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)
         {