Upd libc++ to 0cc34ca7ecfc9d0efee322f60ed6c3169f4f70ca (12 Apr 2022)

15 files changed, 893 insertions, 479 deletions

diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/in_found_result.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/in_found_result.h
index 0864d7c62c..d43f45cd80 100644
--- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/in_found_result.h
+++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/in_found_result.h
@@ -23,20 +23,20 @@
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 namespace ranges {
-template <class _I1>
+template <class _InIter1>
 struct in_found_result {
-  _LIBCPP_NO_UNIQUE_ADDRESS _I1 in;
+  _LIBCPP_NO_UNIQUE_ADDRESS _InIter1 in;
   bool found;
 
-  template <class _I2>
-    requires convertible_to<const _I1&, _I2>
-  _LIBCPP_HIDE_FROM_ABI constexpr operator in_found_result<_I2>() const & {
+  template <class _InIter2>
+    requires convertible_to<const _InIter1&, _InIter2>
+  _LIBCPP_HIDE_FROM_ABI constexpr operator in_found_result<_InIter2>() const & {
     return {in, found};
   }
 
-  template <class _I2>
-    requires convertible_to<_I1, _I2>
-  _LIBCPP_HIDE_FROM_ABI constexpr operator in_found_result<_I2>() && {
+  template <class _InIter2>
+    requires convertible_to<_InIter1, _InIter2>
+  _LIBCPP_HIDE_FROM_ABI constexpr operator in_found_result<_InIter2>() && {
     return {std::move(in), found};
   }
 };
diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/in_fun_result.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/in_fun_result.h
index d502df234a..21efa65506 100644
--- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/in_fun_result.h
+++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/in_fun_result.h
@@ -20,29 +20,29 @@
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-#if _LIBCPP_STD_VER > 17
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
 namespace ranges {
-template <class _Ip, class _Fp>
+template <class _InIter1, class _Func1>
 struct in_fun_result {
-  _LIBCPP_NO_UNIQUE_ADDRESS _Ip in;
-  _LIBCPP_NO_UNIQUE_ADDRESS _Fp fun;
+  _LIBCPP_NO_UNIQUE_ADDRESS _InIter1 in;
+  _LIBCPP_NO_UNIQUE_ADDRESS _Func1 fun;
 
-  template <class _I2, class _F2>
-    requires convertible_to<const _Ip&, _I2> && convertible_to<const _Fp&, _F2>
-  _LIBCPP_HIDE_FROM_ABI constexpr operator in_fun_result<_I2, _F2>() const & {
+  template <class _InIter2, class _Func2>
+    requires convertible_to<const _InIter1&, _InIter2> && convertible_to<const _Func1&, _Func2>
+  _LIBCPP_HIDE_FROM_ABI constexpr operator in_fun_result<_InIter2, _Func2>() const & {
     return {in, fun};
   }
 
-  template <class _I2, class _F2>
-    requires convertible_to<_Ip, _I2> && convertible_to<_Fp, _F2>
-  _LIBCPP_HIDE_FROM_ABI constexpr operator in_fun_result<_I2, _F2>() && {
+  template <class _InIter2, class _Func2>
+    requires convertible_to<_InIter1, _InIter2> && convertible_to<_Func1, _Func2>
+  _LIBCPP_HIDE_FROM_ABI constexpr operator in_fun_result<_InIter2, _Func2>() && {
     return {std::move(in), std::move(fun)};
   }
 };
 } // namespace ranges
 
-#endif // _LIBCPP_STD_VER > 17
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
 _LIBCPP_END_NAMESPACE_STD
 
diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/in_in_out_result.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/in_in_out_result.h
index 9becf4091d..e45fef187e 100644
--- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/in_in_out_result.h
+++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/in_in_out_result.h
@@ -24,24 +24,26 @@ _LIBCPP_BEGIN_NAMESPACE_STD
 
 namespace ranges {
 
-template <class _I1, class _I2, class _O1>
+template <class _InIter1, class _InIter2, class _OutIter1>
 struct in_in_out_result {
-  _LIBCPP_NO_UNIQUE_ADDRESS _I1 in1;
-  _LIBCPP_NO_UNIQUE_ADDRESS _I2 in2;
-  _LIBCPP_NO_UNIQUE_ADDRESS _O1 out;
+  _LIBCPP_NO_UNIQUE_ADDRESS _InIter1 in1;
+  _LIBCPP_NO_UNIQUE_ADDRESS _InIter2 in2;
+  _LIBCPP_NO_UNIQUE_ADDRESS _OutIter1 out;
 
-  template <class _II1, class _II2, class _OO1>
-    requires convertible_to<const _I1&, _II1> && convertible_to<const _I2&, _II2> && convertible_to<const _O1&, _OO1>
+  template <class _InIter3, class _InIter4, class _OutIter2>
+    requires convertible_to<const _InIter1&, _InIter3>
+          && convertible_to<const _InIter2&, _InIter4> && convertible_to<const _OutIter1&, _OutIter2>
   _LIBCPP_HIDE_FROM_ABI constexpr
-  operator in_in_out_result<_II1, _II2, _OO1>() const& {
+  operator in_in_out_result<_InIter3, _InIter4, _OutIter2>() const& {
     return {in1, in2, out};
   }
 
-  template <class _II1, class _II2, class _OO1>
-    requires convertible_to<_I1, _II1> && convertible_to<_I2, _II2> && convertible_to<_O1, _OO1>
+  template <class _InIter3, class _InIter4, class _OutIter2>
+    requires convertible_to<_InIter1, _InIter3>
+          && convertible_to<_InIter2, _InIter4> && convertible_to<_OutIter1, _OutIter2>
   _LIBCPP_HIDE_FROM_ABI constexpr
-  operator in_in_out_result<_II1, _II2, _OO1>() && {
-    return {_VSTD::move(in1), _VSTD::move(in2), _VSTD::move(out)};
+  operator in_in_out_result<_InIter3, _InIter4, _OutIter2>() && {
+    return {std::move(in1), std::move(in2), std::move(out)};
   }
 };
 
diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/in_in_result.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/in_in_result.h
index 80e69a6474..39e64ced33 100644
--- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/in_in_result.h
+++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/in_in_result.h
@@ -20,31 +20,33 @@
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-#if _LIBCPP_STD_VER > 17
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
 namespace ranges {
 
-template <class _I1, class _I2>
+template <class _InIter1, class _InIter2>
 struct in_in_result {
-  _LIBCPP_NO_UNIQUE_ADDRESS _I1 in1;
-  _LIBCPP_NO_UNIQUE_ADDRESS _I2 in2;
+  _LIBCPP_NO_UNIQUE_ADDRESS _InIter1 in1;
+  _LIBCPP_NO_UNIQUE_ADDRESS _InIter2 in2;
 
-  template <class _II1, class _II2>
-    requires convertible_to<const _I1&, _II1> && convertible_to<const _I2&, _II2>
+  template <class _InIter3, class _InIter4>
+    requires convertible_to<const _InIter1&, _InIter3> && convertible_to<const _InIter2&, _InIter4>
    _LIBCPP_HIDE_FROM_ABI constexpr
-   operator in_in_result<_II1, _II2>() const & {
+   operator in_in_result<_InIter3, _InIter4>() const & {
     return {in1, in2};
   }
 
-  template <class _II1, class _II2>
-    requires convertible_to<_I1, _II1> && convertible_to<_I2, _II2>
+  template <class _InIter3, class _InIter4>
+    requires convertible_to<_InIter1, _InIter3> && convertible_to<_InIter2, _InIter4>
   _LIBCPP_HIDE_FROM_ABI constexpr
-  operator in_in_result<_II1, _II2>() && { return {_VSTD::move(in1), _VSTD::move(in2)}; }
+  operator in_in_result<_InIter3, _InIter4>() && {
+    return {std::move(in1), std::move(in2)};
+  }
 };
 
 } // namespace ranges
 
-#endif // _LIBCPP_STD_VER > 17
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
 _LIBCPP_END_NAMESPACE_STD
 
diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/in_out_out_result.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/in_out_out_result.h
index 2125edf2f2..52a883b176 100644
--- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/in_out_out_result.h
+++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/in_out_out_result.h
@@ -20,32 +20,34 @@
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-#if _LIBCPP_STD_VER > 17
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
 namespace ranges {
-template <class _I1, class _O1, class _O2>
+template <class _InIter1, class _OutIter1, class _OutIter2>
 struct in_out_out_result {
-  _LIBCPP_NO_UNIQUE_ADDRESS _I1 in;
-  _LIBCPP_NO_UNIQUE_ADDRESS _O1 out1;
-  _LIBCPP_NO_UNIQUE_ADDRESS _O2 out2;
+  _LIBCPP_NO_UNIQUE_ADDRESS _InIter1 in;
+  _LIBCPP_NO_UNIQUE_ADDRESS _OutIter1 out1;
+  _LIBCPP_NO_UNIQUE_ADDRESS _OutIter2 out2;
 
-  template <class _II1, class _OO1, class _OO2>
-    requires convertible_to<const _I1&, _II1> && convertible_to<const _O1&, _OO1> && convertible_to<const _O2&, _OO2>
+  template <class _InIter2, class _OutIter3, class _OutIter4>
+    requires convertible_to<const _InIter1&, _InIter2>
+          && convertible_to<const _OutIter1&, _OutIter3> && convertible_to<const _OutIter2&, _OutIter4>
   _LIBCPP_HIDE_FROM_ABI constexpr
-  operator in_out_out_result<_II1, _OO1, _OO2>() const& {
+  operator in_out_out_result<_InIter2, _OutIter3, _OutIter4>() const& {
     return {in, out1, out2};
   }
 
-  template <class _II1, class _OO1, class _OO2>
-    requires convertible_to<_I1, _II1> && convertible_to<_O1, _OO1> && convertible_to<_O2, _OO2>
+  template <class _InIter2, class _OutIter3, class _OutIter4>
+    requires convertible_to<_InIter1, _InIter2>
+          && convertible_to<_OutIter1, _OutIter3> && convertible_to<_OutIter2, _OutIter4>
   _LIBCPP_HIDE_FROM_ABI constexpr
-  operator in_out_out_result<_II1, _OO1, _OO2>() && {
-    return {_VSTD::move(in), _VSTD::move(out1), _VSTD::move(out2)};
+  operator in_out_out_result<_InIter2, _OutIter3, _OutIter4>() && {
+    return {std::move(in), std::move(out1), std::move(out2)};
   }
 };
 } // namespace ranges
 
-#endif // _LIBCPP_STD_VER > 17
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
 _LIBCPP_END_NAMESPACE_STD
 
diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/in_out_result.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/in_out_result.h
index 03e9080871..47e6f39079 100644
--- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/in_out_result.h
+++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/in_out_result.h
@@ -24,24 +24,23 @@ _LIBCPP_BEGIN_NAMESPACE_STD
 
 namespace ranges {
 
-template<class _InputIterator, class _OutputIterator>
+template<class _InIter1, class _OutIter1>
 struct in_out_result {
-  _LIBCPP_NO_UNIQUE_ADDRESS _InputIterator in;
-  _LIBCPP_NO_UNIQUE_ADDRESS _OutputIterator out;
+  _LIBCPP_NO_UNIQUE_ADDRESS _InIter1 in;
+  _LIBCPP_NO_UNIQUE_ADDRESS _OutIter1 out;
 
-  template <class _InputIterator2, class _OutputIterator2>
-    requires convertible_to<const _InputIterator&, _InputIterator2> && convertible_to<const _OutputIterator&,
-                           _OutputIterator2>
+  template <class _InIter2, class _OutIter2>
+    requires convertible_to<const _InIter1&, _InIter2> && convertible_to<const _OutIter1&, _OutIter2>
   _LIBCPP_HIDE_FROM_ABI
-  constexpr operator in_out_result<_InputIterator2, _OutputIterator2>() const & {
+  constexpr operator in_out_result<_InIter2, _OutIter2>() const & {
     return {in, out};
   }
 
-  template <class _InputIterator2, class _OutputIterator2>
-    requires convertible_to<_InputIterator, _InputIterator2> && convertible_to<_OutputIterator, _OutputIterator2>
+  template <class _InIter2, class _OutIter2>
+    requires convertible_to<_InIter1, _InIter2> && convertible_to<_OutIter1, _OutIter2>
   _LIBCPP_HIDE_FROM_ABI
-  constexpr operator in_out_result<_InputIterator2, _OutputIterator2>() && {
-    return {_VSTD::move(in), _VSTD::move(out)};
+  constexpr operator in_out_result<_InIter2, _OutIter2>() && {
+    return {std::move(in), std::move(out)};
   }
 };
 
diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/min_max_result.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/min_max_result.h
index 6640866c5b..ca77dcc572 100644
--- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/min_max_result.h
+++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/min_max_result.h
@@ -53,4 +53,4 @@ _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
-#endif
+#endif // _LIBCPP___ALGORITHM_MIN_MAX_RESULT_H
diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_count.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_count.h
new file mode 100644
index 0000000000..3cbcdc959d
--- /dev/null
+++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_count.h
@@ -0,0 +1,61 @@
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___ALGORITHM_RANGES_COUNT_H
+#define _LIBCPP___ALGORITHM_RANGES_COUNT_H
+
+#include <__algorithm/ranges_count_if.h>
+#include <__config>
+#include <__functional/identity.h>
+#include <__functional/ranges_operations.h>
+#include <__iterator/concepts.h>
+#include <__iterator/incrementable_traits.h>
+#include <__iterator/projected.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__utility/move.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace ranges {
+namespace __count {
+struct __fn {
+  template <input_iterator _Iter, sentinel_for<_Iter> _Sent, class _Type, class _Proj = identity>
+    requires indirect_binary_predicate<ranges::equal_to, projected<_Iter, _Proj>, const _Type*>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  iter_difference_t<_Iter> operator()(_Iter __first, _Sent __last, const _Type& __value, _Proj __proj = {}) const {
+    auto __pred = [&](auto&& __e) { return __e == __value; };
+    return ranges::__count_if_impl(std::move(__first), std::move(__last), __pred, __proj);
+  }
+
+  template <input_range _Range, class _Type, class _Proj = identity>
+    requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<_Range>, _Proj>, const _Type*>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  range_difference_t<_Range> operator()(_Range&& __r, const _Type& __value, _Proj __proj = {}) const {
+    auto __pred = [&](auto&& __e) { return __e == __value; };
+    return ranges::__count_if_impl(ranges::begin(__r), ranges::end(__r), __pred, __proj);
+  }
+};
+} // namespace __count
+
+inline namespace __cpo {
+  inline constexpr auto count = __count::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+#endif // _LIBCPP___ALGORITHM_RANGES_COUNT_H
diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_count_if.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_count_if.h
new file mode 100644
index 0000000000..9080631f62
--- /dev/null
+++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_count_if.h
@@ -0,0 +1,71 @@
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___ALGORITHM_RANGES_COUNT_IF_H
+#define _LIBCPP___ALGORITHM_RANGES_COUNT_IF_H
+
+#include <__config>
+#include <__functional/identity.h>
+#include <__functional/invoke.h>
+#include <__functional/ranges_operations.h>
+#include <__iterator/concepts.h>
+#include <__iterator/incrementable_traits.h>
+#include <__iterator/projected.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__utility/move.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace ranges {
+template <class _Iter, class _Sent, class _Proj, class _Pred>
+_LIBCPP_HIDE_FROM_ABI constexpr
+iter_difference_t<_Iter> __count_if_impl(_Iter __first, _Sent __last,
+                                             _Pred& __pred, _Proj& __proj) {
+  iter_difference_t<_Iter> __counter(0);
+  for (; __first != __last; ++__first) {
+    if (std::invoke(__pred, std::invoke(__proj, *__first)))
+      ++__counter;
+  }
+  return __counter;
+}
+
+namespace __count_if {
+struct __fn {
+  template <input_iterator _Iter, sentinel_for<_Iter> _Sent, class _Proj = identity,
+            indirect_unary_predicate<projected<_Iter, _Proj>> _Predicate>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  iter_difference_t<_Iter> operator()(_Iter __first, _Sent __last, _Predicate __pred, _Proj __proj = {}) const {
+    return ranges::__count_if_impl(std::move(__first), std::move(__last), __pred, __proj);
+  }
+
+  template <input_range _Range, class _Proj = identity,
+            indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Predicate>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  range_difference_t<_Range> operator()(_Range&& __r, _Predicate __pred, _Proj __proj = {}) const {
+    return ranges::__count_if_impl(ranges::begin(__r), ranges::end(__r), __pred, __proj);
+  }
+};
+} // namespace __count_if
+
+inline namespace __cpo {
+  inline constexpr auto count_if = __count_if::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+#endif // _LIBCPP___ALGORITHM_RANGES_COUNT_IF_H
diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_max.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_max.h
new file mode 100644
index 0000000000..f48bc3ecec
--- /dev/null
+++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_max.h
@@ -0,0 +1,93 @@
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___ALGORITHM_RANGES_MAX_H
+#define _LIBCPP___ALGORITHM_RANGES_MAX_H
+
+#include <__algorithm/ranges_min_element.h>
+#include <__assert>
+#include <__concepts/copyable.h>
+#include <__config>
+#include <__functional/identity.h>
+#include <__functional/invoke.h>
+#include <__functional/ranges_operations.h>
+#include <__iterator/concepts.h>
+#include <__iterator/projected.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__utility/move.h>
+#include <initializer_list>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace ranges {
+namespace __max {
+struct __fn {
+  template <class _Tp, class _Proj = identity,
+            indirect_strict_weak_order<projected<const _Tp*, _Proj>> _Comp = ranges::less>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  const _Tp& operator()(const _Tp& __a, const _Tp& __b, _Comp __comp = {}, _Proj __proj = {}) const {
+    return std::invoke(__comp, std::invoke(__proj, __a), std::invoke(__proj, __b)) ? __b : __a;
+  }
+
+  template <copyable _Tp, class _Proj = identity,
+            indirect_strict_weak_order<projected<const _Tp*, _Proj>> _Comp = ranges::less>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  _Tp operator()(initializer_list<_Tp> __il, _Comp __comp = {}, _Proj __proj = {}) const {
+    _LIBCPP_ASSERT(__il.begin() != __il.end(), "initializer_list must contain at least one element");
+
+    auto __comp_lhs_rhs_swapped = [&](auto&& __lhs, auto&& __rhs) { return std::invoke(__comp, __rhs, __lhs); };
+    return *ranges::__min_element_impl(__il.begin(), __il.end(), __comp_lhs_rhs_swapped, __proj);
+  }
+
+  template <input_range _Rp, class _Proj = identity,
+            indirect_strict_weak_order<projected<iterator_t<_Rp>, _Proj>> _Comp = ranges::less>
+    requires indirectly_copyable_storable<iterator_t<_Rp>, range_value_t<_Rp>*>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  range_value_t<_Rp> operator()(_Rp&& __r, _Comp __comp = {}, _Proj __proj = {}) const {
+    auto __first = ranges::begin(__r);
+    auto __last = ranges::end(__r);
+
+    _LIBCPP_ASSERT(__first != __last, "range must contain at least one element");
+
+    if constexpr (forward_range<_Rp>) {
+      auto __comp_lhs_rhs_swapped = [&](auto&& __lhs, auto&& __rhs) { return std::invoke(__comp, __rhs, __lhs); };
+      return *ranges::__min_element_impl(std::move(__first), std::move(__last), __comp_lhs_rhs_swapped, __proj);
+    } else {
+      range_value_t<_Rp> __result = *__first;
+      while (++__first != __last) {
+        if (std::invoke(__comp, std::invoke(__proj, __result), std::invoke(__proj, *__first)))
+          __result = *__first;
+      }
+      return __result;
+    }
+  }
+};
+} // namespace __max
+
+inline namespace __cpo {
+  inline constexpr auto max = __max::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP_STD_VER > 17 && && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+#endif // _LIBCPP___ALGORITHM_RANGES_MAX_H
diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_max_element.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_max_element.h
index 230e513962..2ec464a52d 100644
--- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_max_element.h
+++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_max_element.h
@@ -9,6 +9,7 @@
 #ifndef _LIBCPP___ALGORITHM_RANGES_MAX_ELEMENT_H
 #define _LIBCPP___ALGORITHM_RANGES_MAX_ELEMENT_H
 
+#include <__algorithm/ranges_min_element.h>
 #include <__config>
 #include <__functional/identity.h>
 #include <__functional/invoke.h>
@@ -30,31 +31,20 @@ _LIBCPP_BEGIN_NAMESPACE_STD
 namespace ranges {
 namespace __max_element {
 struct __fn {
-  template <class _Ip, class _Sp, class _Proj, class _Comp>
-  _LIBCPP_HIDE_FROM_ABI static constexpr
-  _Ip __go(_Ip __first, _Sp __last, _Comp& __comp, _Proj& __proj) {
-    if (__first == __last)
-      return __first;
-
-    _Ip __i = __first;
-    while (++__i != __last)
-      if (std::invoke(__comp, std::invoke(__proj, *__first), std::invoke(__proj, *__i)))
-        __first = __i;
-    return __first;
-  }
-
   template <forward_iterator _Ip, sentinel_for<_Ip> _Sp, class _Proj = identity,
             indirect_strict_weak_order<projected<_Ip, _Proj>> _Comp = ranges::less>
   _LIBCPP_HIDE_FROM_ABI constexpr
   _Ip operator()(_Ip __first, _Sp __last, _Comp __comp = {}, _Proj __proj = {}) const {
-    return __go(__first, __last, __comp, __proj);
+    auto __comp_lhs_rhs_swapped = [&](auto&& __lhs, auto&& __rhs) { return std::invoke(__comp, __rhs, __lhs); };
+    return __min_element_impl(__first, __last, __comp_lhs_rhs_swapped, __proj);
   }
 
   template <forward_range _Rp, class _Proj = identity,
             indirect_strict_weak_order<projected<iterator_t<_Rp>, _Proj>> _Comp = ranges::less>
   _LIBCPP_HIDE_FROM_ABI constexpr
   borrowed_iterator_t<_Rp> operator()(_Rp&& __r, _Comp __comp = {}, _Proj __proj = {}) const {
-    return __go(ranges::begin(__r), ranges::end(__r), __comp, __proj);
+    auto __comp_lhs_rhs_swapped = [&](auto&& __lhs, auto&& __rhs) { return std::invoke(__comp, __rhs, __lhs); };
+    return __min_element_impl(ranges::begin(__r), ranges::end(__r), __comp_lhs_rhs_swapped, __proj);
   }
 };
 } // namespace __max_element
diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_mismatch.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_mismatch.h
index 4775daf4f7..4c1440b5da 100644
--- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_mismatch.h
+++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_mismatch.h
@@ -27,7 +27,7 @@
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-#if _LIBCPP_STD_VER > 17
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
 namespace ranges {
 
@@ -78,7 +78,7 @@ inline namespace __cpo {
 } // namespace __cpo
 } // namespace ranges
 
-#endif // _LIBCPP_STD_VER > 17
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
 _LIBCPP_END_NAMESPACE_STD
 
diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_swap_ranges.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_swap_ranges.h
index 18067ff3ba..3254e1c60a 100644
--- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_swap_ranges.h
+++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_swap_ranges.h
@@ -22,7 +22,7 @@
 #  pragma GCC system_header
 #endif
 
-#if _LIBCPP_STD_VER > 17
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
@@ -64,6 +64,6 @@ inline namespace __cpo {
 
 _LIBCPP_END_NAMESPACE_STD
 
-#endif // _LIBCPP_STD_VER > 17
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
 #endif // _LIBCPP___ALGORITHM_RANGES_SWAP_RANGES_H
diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_transform.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_transform.h
new file mode 100644
index 0000000000..3c13b1b79f
--- /dev/null
+++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/ranges_transform.h
@@ -0,0 +1,170 @@
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___ALGORITHM_RANGES_TRANSFORM_H
+#define _LIBCPP___ALGORITHM_RANGES_TRANSFORM_H
+
+#include <__algorithm/in_in_out_result.h>
+#include <__algorithm/in_out_result.h>
+#include <__concepts/constructible.h>
+#include <__config>
+#include <__functional/identity.h>
+#include <__functional/invoke.h>
+#include <__iterator/concepts.h>
+#include <__iterator/projected.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__ranges/dangling.h>
+#include <__utility/move.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace ranges {
+
+template <class _Ip, class _Op>
+using unary_transform_result = in_out_result<_Ip, _Op>;
+
+template <class _I1, class _I2, class _O1>
+using binary_transform_result = in_in_out_result<_I1, _I2, _O1>;
+
+namespace __transform {
+struct __fn {
+private:
+  template <class _InIter, class _Sent,
+            class _OutIter,
+            class _Func,
+            class _Proj>
+  _LIBCPP_HIDE_FROM_ABI static constexpr
+  unary_transform_result<_InIter, _OutIter> __unary(_InIter __first, _Sent __last,
+                                                    _OutIter __result,
+                                                    _Func& __operation,
+                                                    _Proj& __projection) {
+    while (__first != __last) {
+      *__result = std::invoke(__operation, std::invoke(__projection, *__first));
+      ++__first;
+      ++__result;
+    }
+
+    return {std::move(__first), std::move(__result)};
+  }
+
+  template <class _InIter1, class _Sent1,
+            class _InIter2, class _Sent2,
+            class _OutIter,
+            class _Func,
+            class _Proj1,
+            class _Proj2>
+  _LIBCPP_HIDE_FROM_ABI static constexpr binary_transform_result<_InIter1, _InIter2, _OutIter>
+  __binary(_InIter1 __first1, _Sent1 __last1,
+           _InIter2 __first2, _Sent2 __last2,
+           _OutIter __result,
+           _Func& __binary_operation,
+           _Proj1& __projection1,
+           _Proj2& __projection2) {
+    while (__first1 != __last1 && __first2 != __last2) {
+      *__result = std::invoke(__binary_operation, std::invoke(__projection1, *__first1),
+                                                  std::invoke(__projection2, *__first2));
+      ++__first1;
+      ++__first2;
+      ++__result;
+    }
+    return {std::move(__first1), std::move(__first2), std::move(__result)};
+  }
+public:
+  template <input_iterator _InIter, sentinel_for<_InIter> _Sent,
+            weakly_incrementable _OutIter,
+            copy_constructible _Func,
+            class _Proj = identity>
+    requires indirectly_writable<_OutIter, indirect_result_t<_Func&, projected<_InIter, _Proj>>>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  unary_transform_result<_InIter, _OutIter> operator()(_InIter __first, _Sent __last,
+                                                       _OutIter __result,
+                                                       _Func __operation,
+                                                       _Proj __proj = {}) const {
+    return __unary(std::move(__first), std::move(__last), std::move(__result), __operation, __proj);
+  }
+
+  template <input_range _Range,
+            weakly_incrementable _OutIter,
+            copy_constructible _Func,
+            class _Proj = identity>
+    requires indirectly_writable<_OutIter, indirect_result_t<_Func, projected<iterator_t<_Range>, _Proj>>>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  unary_transform_result<borrowed_iterator_t<_Range>, _OutIter> operator()(_Range&& __range,
+                                                                           _OutIter __result,
+                                                                           _Func __operation,
+                                                                           _Proj __projection = {}) const {
+    return __unary(ranges::begin(__range), ranges::end(__range), std::move(__result), __operation, __projection);
+  }
+
+  template <input_iterator _InIter1, sentinel_for<_InIter1> _Sent1,
+            input_iterator _InIter2, sentinel_for<_InIter2> _Sent2,
+            weakly_incrementable _OutIter,
+            copy_constructible _Func,
+            class _Proj1 = identity,
+            class _Proj2 = identity>
+    requires indirectly_writable<_OutIter, indirect_result_t<_Func&, projected<_InIter1, _Proj1>,
+                                                                     projected<_InIter2, _Proj2>>>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  binary_transform_result<_InIter1, _InIter2, _OutIter> operator()(_InIter1 __first1, _Sent1 __last1,
+                                                                   _InIter2 __first2, _Sent2 __last2,
+                                                                   _OutIter __result,
+                                                                   _Func __binary_operation,
+                                                                   _Proj1 __projection1 = {},
+                                                                   _Proj2 __projection2 = {}) const {
+    return __binary(std::move(__first1), std::move(__last1),
+                    std::move(__first2), std::move(__last2),
+                    std::move(__result),
+                    __binary_operation,
+                    __projection1,
+                    __projection2);
+  }
+
+  template <input_range _Range1,
+            input_range _Range2,
+            weakly_incrementable _OutIter,
+            copy_constructible _Func,
+            class _Proj1 = identity,
+            class _Proj2 = identity>
+    requires indirectly_writable<_OutIter, indirect_result_t<_Func&, projected<iterator_t<_Range1>, _Proj1>,
+                                                                     projected<iterator_t<_Range2>, _Proj2>>>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  binary_transform_result<borrowed_iterator_t<_Range1>, borrowed_iterator_t<_Range2>, _OutIter>
+  operator()(_Range1&& __range1,
+             _Range2&& __range2,
+             _OutIter __result,
+             _Func __binary_operation,
+             _Proj1 __projection1 = {},
+             _Proj2 __projection2 = {}) const {
+    return __binary(ranges::begin(__range1), ranges::end(__range1),
+                    ranges::begin(__range2), ranges::end(__range2),
+                    std::move(__result),
+                    __binary_operation,
+                    __projection1,
+                    __projection2);
+  }
+
+};
+} // namespace __transform
+
+inline namespace __cpo {
+  inline constexpr auto transform = __transform::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+#endif // _LIBCPP___ALGORITHM_RANGES_TRANSFORM_H
diff --git a/contrib/libs/cxxsupp/libcxx/include/__algorithm/sort.h b/contrib/libs/cxxsupp/libcxx/include/__algorithm/sort.h
index 27ce647c81..d108dc31bd 100644
--- a/contrib/libs/cxxsupp/libcxx/include/__algorithm/sort.h
+++ b/contrib/libs/cxxsupp/libcxx/include/__algorithm/sort.h
@@ -31,438 +31,469 @@ _LIBCPP_BEGIN_NAMESPACE_STD
 // stable, 2-3 compares, 0-2 swaps
 
 template <class _Compare, class _ForwardIterator>
-_LIBCPP_CONSTEXPR_AFTER_CXX11 unsigned
-__sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, _Compare __c)
-{
-    unsigned __r = 0;
-    if (!__c(*__y, *__x))          // if x <= y
+_LIBCPP_CONSTEXPR_AFTER_CXX11 unsigned __sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z,
+                                               _Compare __c) {
+  unsigned __r = 0;
+  if (!__c(*__y, *__x))   // if x <= y
+  {
+    if (!__c(*__z, *__y)) // if y <= z
+      return __r;         // x <= y && y <= z
+                          // x <= y && y > z
+    swap(*__y, *__z);     // x <= z && y < z
+    __r = 1;
+    if (__c(*__y, *__x))  // if x > y
     {
-        if (!__c(*__z, *__y))      // if y <= z
-            return __r;            // x <= y && y <= z
-                                   // x <= y && y > z
-        swap(*__y, *__z);          // x <= z && y < z
-        __r = 1;
-        if (__c(*__y, *__x))       // if x > y
-        {
-            swap(*__x, *__y);      // x < y && y <= z
-            __r = 2;
-        }
-        return __r;                // x <= y && y < z
-    }
-    if (__c(*__z, *__y))           // x > y, if y > z
-    {
-        swap(*__x, *__z);          // x < y && y < z
-        __r = 1;
-        return __r;
-    }
-    swap(*__x, *__y);              // x > y && y <= z
-    __r = 1;                       // x < y && x <= z
-    if (__c(*__z, *__y))           // if y > z
-    {
-        swap(*__y, *__z);          // x <= y && y < z
-        __r = 2;
+      swap(*__x, *__y);   // x < y && y <= z
+      __r = 2;
     }
+    return __r;           // x <= y && y < z
+  }
+  if (__c(*__z, *__y))    // x > y, if y > z
+  {
+    swap(*__x, *__z);     // x < y && y < z
+    __r = 1;
     return __r;
-}                                  // x <= y && y <= z
+  }
+  swap(*__x, *__y);       // x > y && y <= z
+  __r = 1;                // x < y && x <= z
+  if (__c(*__z, *__y))    // if y > z
+  {
+    swap(*__y, *__z);     // x <= y && y < z
+    __r = 2;
+  }
+  return __r;
+}                         // x <= y && y <= z
 
 // stable, 3-6 compares, 0-5 swaps
 
 template <class _Compare, class _ForwardIterator>
-unsigned
-__sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
-            _ForwardIterator __x4, _Compare __c)
-{
-    unsigned __r = _VSTD::__sort3<_Compare>(__x1, __x2, __x3, __c);
-    if (__c(*__x4, *__x3))
-    {
-        swap(*__x3, *__x4);
+unsigned __sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, _ForwardIterator __x4,
+                 _Compare __c) {
+  unsigned __r = _VSTD::__sort3<_Compare>(__x1, __x2, __x3, __c);
+  if (__c(*__x4, *__x3)) {
+    swap(*__x3, *__x4);
+    ++__r;
+    if (__c(*__x3, *__x2)) {
+      swap(*__x2, *__x3);
+      ++__r;
+      if (__c(*__x2, *__x1)) {
+        swap(*__x1, *__x2);
         ++__r;
-        if (__c(*__x3, *__x2))
-        {
-            swap(*__x2, *__x3);
-            ++__r;
-            if (__c(*__x2, *__x1))
-            {
-                swap(*__x1, *__x2);
-                ++__r;
-            }
-        }
+      }
     }
-    return __r;
+  }
+  return __r;
 }
 
 // stable, 4-10 compares, 0-9 swaps
 
 template <class _Compare, class _ForwardIterator>
-_LIBCPP_HIDDEN
-unsigned
-__sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
-            _ForwardIterator __x4, _ForwardIterator __x5, _Compare __c)
-{
-    unsigned __r = _VSTD::__sort4<_Compare>(__x1, __x2, __x3, __x4, __c);
-    if (__c(*__x5, *__x4))
-    {
-        swap(*__x4, *__x5);
+_LIBCPP_HIDDEN unsigned __sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
+                                _ForwardIterator __x4, _ForwardIterator __x5, _Compare __c) {
+  unsigned __r = _VSTD::__sort4<_Compare>(__x1, __x2, __x3, __x4, __c);
+  if (__c(*__x5, *__x4)) {
+    swap(*__x4, *__x5);
+    ++__r;
+    if (__c(*__x4, *__x3)) {
+      swap(*__x3, *__x4);
+      ++__r;
+      if (__c(*__x3, *__x2)) {
+        swap(*__x2, *__x3);
         ++__r;
-        if (__c(*__x4, *__x3))
-        {
-            swap(*__x3, *__x4);
-            ++__r;
-            if (__c(*__x3, *__x2))
-            {
-                swap(*__x2, *__x3);
-                ++__r;
-                if (__c(*__x2, *__x1))
-                {
-                    swap(*__x1, *__x2);
-                    ++__r;
-                }
-            }
+        if (__c(*__x2, *__x1)) {
+          swap(*__x1, *__x2);
+          ++__r;
         }
+      }
     }
-    return __r;
+  }
+  return __r;
+}
+
+template <class _Tp>
+struct __is_simple_comparator : false_type {};
+template <class _Tp>
+struct __is_simple_comparator<__less<_Tp>&> : true_type {};
+template <class _Tp>
+struct __is_simple_comparator<less<_Tp>&> : true_type {};
+template <class _Tp>
+struct __is_simple_comparator<greater<_Tp>&> : true_type {};
+
+template <class _Compare, class _Iter, class _Tp = typename iterator_traits<_Iter>::value_type>
+using __use_branchless_sort =
+    integral_constant<bool, __is_cpp17_contiguous_iterator<_Iter>::value && sizeof(_Tp) <= sizeof(void*) &&
+                                is_arithmetic<_Tp>::value && __is_simple_comparator<_Compare>::value>;
+
+// Ensures that __c(*__x, *__y) is true by swapping *__x and *__y if necessary.
+template <class _Compare, class _RandomAccessIterator>
+inline _LIBCPP_HIDE_FROM_ABI 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 <class _Compare, class _RandomAccessIterator>
+inline _LIBCPP_HIDE_FROM_ABI 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 <class _Compare, class _RandomAccessIterator>
+inline _LIBCPP_HIDE_FROM_ABI __enable_if_t<__use_branchless_sort<_Compare, _RandomAccessIterator>::value, void>
+__sort3_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3,
+                         _Compare __c) {
+  _VSTD::__cond_swap<_Compare>(__x2, __x3, __c);
+  _VSTD::__partially_sorted_swap<_Compare>(__x1, __x2, __x3, __c);
+}
+
+template <class _Compare, class _RandomAccessIterator>
+inline _LIBCPP_HIDE_FROM_ABI __enable_if_t<!__use_branchless_sort<_Compare, _RandomAccessIterator>::value, void>
+__sort3_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3,
+                         _Compare __c) {
+  _VSTD::__sort3<_Compare>(__x1, __x2, __x3, __c);
+}
+
+template <class _Compare, class _RandomAccessIterator>
+inline _LIBCPP_HIDE_FROM_ABI __enable_if_t<__use_branchless_sort<_Compare, _RandomAccessIterator>::value, void>
+__sort4_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3,
+                         _RandomAccessIterator __x4, _Compare __c) {
+  _VSTD::__cond_swap<_Compare>(__x1, __x3, __c);
+  _VSTD::__cond_swap<_Compare>(__x2, __x4, __c);
+  _VSTD::__cond_swap<_Compare>(__x1, __x2, __c);
+  _VSTD::__cond_swap<_Compare>(__x3, __x4, __c);
+  _VSTD::__cond_swap<_Compare>(__x2, __x3, __c);
+}
+
+template <class _Compare, class _RandomAccessIterator>
+inline _LIBCPP_HIDE_FROM_ABI __enable_if_t<!__use_branchless_sort<_Compare, _RandomAccessIterator>::value, void>
+__sort4_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3,
+                         _RandomAccessIterator __x4, _Compare __c) {
+  _VSTD::__sort4<_Compare>(__x1, __x2, __x3, __x4, __c);
+}
+
+template <class _Compare, class _RandomAccessIterator>
+inline _LIBCPP_HIDE_FROM_ABI __enable_if_t<__use_branchless_sort<_Compare, _RandomAccessIterator>::value, void>
+__sort5_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3,
+                         _RandomAccessIterator __x4, _RandomAccessIterator __x5, _Compare __c) {
+  _VSTD::__cond_swap<_Compare>(__x1, __x2, __c);
+  _VSTD::__cond_swap<_Compare>(__x4, __x5, __c);
+  _VSTD::__partially_sorted_swap<_Compare>(__x3, __x4, __x5, __c);
+  _VSTD::__cond_swap<_Compare>(__x2, __x5, __c);
+  _VSTD::__partially_sorted_swap<_Compare>(__x1, __x3, __x4, __c);
+  _VSTD::__partially_sorted_swap<_Compare>(__x2, __x3, __x4, __c);
+}
+
+template <class _Compare, class _RandomAccessIterator>
+inline _LIBCPP_HIDE_FROM_ABI __enable_if_t<!__use_branchless_sort<_Compare, _RandomAccessIterator>::value, void>
+__sort5_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3,
+                         _RandomAccessIterator __x4, _RandomAccessIterator __x5, _Compare __c) {
+  _VSTD::__sort5<_Compare>(__x1, __x2, __x3, __x4, __x5, __c);
 }
 
 // Assumes size > 0
 template <class _Compare, class _BidirectionalIterator>
-_LIBCPP_CONSTEXPR_AFTER_CXX11 void
-__selection_sort(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
-{
-    _BidirectionalIterator __lm1 = __last;
-    for (--__lm1; __first != __lm1; ++__first)
-    {
-        _BidirectionalIterator __i = _VSTD::min_element(__first, __last, __comp);
-        if (__i != __first)
-            swap(*__first, *__i);
-    }
+_LIBCPP_CONSTEXPR_AFTER_CXX11 void __selection_sort(_BidirectionalIterator __first, _BidirectionalIterator __last,
+                                                    _Compare __comp) {
+  _BidirectionalIterator __lm1 = __last;
+  for (--__lm1; __first != __lm1; ++__first) {
+    _BidirectionalIterator __i = _VSTD::min_element(__first, __last, __comp);
+    if (__i != __first)
+      swap(*__first, *__i);
+  }
 }
 
 template <class _Compare, class _BidirectionalIterator>
-void
-__insertion_sort(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
-{
-    typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
-    if (__first != __last)
-    {
-        _BidirectionalIterator __i = __first;
-        for (++__i; __i != __last; ++__i)
-        {
-            _BidirectionalIterator __j = __i;
-            value_type __t(_VSTD::move(*__j));
-            for (_BidirectionalIterator __k = __i; __k != __first && __comp(__t,  *--__k); --__j)
-                *__j = _VSTD::move(*__k);
-            *__j = _VSTD::move(__t);
-        }
+void __insertion_sort(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) {
+  typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
+  if (__first != __last) {
+    _BidirectionalIterator __i = __first;
+    for (++__i; __i != __last; ++__i) {
+      _BidirectionalIterator __j = __i;
+      value_type __t(_VSTD::move(*__j));
+      for (_BidirectionalIterator __k = __i; __k != __first && __comp(__t, *--__k); --__j)
+        *__j = _VSTD::move(*__k);
+      *__j = _VSTD::move(__t);
     }
+  }
 }
 
 template <class _Compare, class _RandomAccessIterator>
-void
-__insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
-{
-    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);
-    for (_RandomAccessIterator __i = __j+difference_type(1); __i != __last; ++__i)
-    {
-        if (__comp(*__i, *__j))
-        {
-            value_type __t(_VSTD::move(*__i));
-            _RandomAccessIterator __k = __j;
-            __j = __i;
-            do
-            {
-                *__j = _VSTD::move(*__k);
-                __j = __k;
-            } while (__j != __first && __comp(__t, *--__k));
-            *__j = _VSTD::move(__t);
-        }
-        __j = __i;
+void __insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
+  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_maybe_branchless<_Compare>(__first, __first + difference_type(1), __j, __comp);
+  for (_RandomAccessIterator __i = __j + difference_type(1); __i != __last; ++__i) {
+    if (__comp(*__i, *__j)) {
+      value_type __t(_VSTD::move(*__i));
+      _RandomAccessIterator __k = __j;
+      __j = __i;
+      do {
+        *__j = _VSTD::move(*__k);
+        __j = __k;
+      } while (__j != __first && __comp(__t, *--__k));
+      *__j = _VSTD::move(__t);
     }
+    __j = __i;
+  }
 }
 
 template <class _Compare, class _RandomAccessIterator>
-bool
-__insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
-{
-    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
-    switch (__last - __first)
-    {
+bool __insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
+  typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
+  switch (__last - __first) {
+  case 0:
+  case 1:
+    return true;
+  case 2:
+    if (__comp(*--__last, *__first))
+      swap(*__first, *__last);
+    return true;
+  case 3:
+    _VSTD::__sort3_maybe_branchless<_Compare>(__first, __first + difference_type(1), --__last, __comp);
+    return true;
+  case 4:
+    _VSTD::__sort4_maybe_branchless<_Compare>(__first, __first + difference_type(1), __first + difference_type(2),
+                                              --__last, __comp);
+    return true;
+  case 5:
+    _VSTD::__sort5_maybe_branchless<_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_maybe_branchless<_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) {
+    if (__comp(*__i, *__j)) {
+      value_type __t(_VSTD::move(*__i));
+      _RandomAccessIterator __k = __j;
+      __j = __i;
+      do {
+        *__j = _VSTD::move(*__k);
+        __j = __k;
+      } while (__j != __first && __comp(__t, *--__k));
+      *__j = _VSTD::move(__t);
+      if (++__count == __limit)
+        return ++__i == __last;
+    }
+    __j = __i;
+  }
+  return true;
+}
+
+template <class _Compare, class _BidirectionalIterator>
+void __insertion_sort_move(_BidirectionalIterator __first1, _BidirectionalIterator __last1,
+                           typename iterator_traits<_BidirectionalIterator>::value_type* __first2, _Compare __comp) {
+  typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
+  if (__first1 != __last1) {
+    __destruct_n __d(0);
+    unique_ptr<value_type, __destruct_n&> __h(__first2, __d);
+    value_type* __last2 = __first2;
+    ::new ((void*)__last2) value_type(_VSTD::move(*__first1));
+    __d.template __incr<value_type>();
+    for (++__last2; ++__first1 != __last1; ++__last2) {
+      value_type* __j2 = __last2;
+      value_type* __i2 = __j2;
+      if (__comp(*__first1, *--__i2)) {
+        ::new ((void*)__j2) value_type(_VSTD::move(*__i2));
+        __d.template __incr<value_type>();
+        for (--__j2; __i2 != __first2 && __comp(*__first1, *--__i2); --__j2)
+          *__j2 = _VSTD::move(*__i2);
+        *__j2 = _VSTD::move(*__first1);
+      } else {
+        ::new ((void*)__j2) value_type(_VSTD::move(*__first1));
+        __d.template __incr<value_type>();
+      }
+    }
+    __h.release();
+  }
+}
+
+template <class _Compare, class _RandomAccessIterator>
+void __introsort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
+                 typename iterator_traits<_RandomAccessIterator>::difference_type __depth) {
+  typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
+  typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
+  const difference_type __limit =
+      is_trivially_copy_constructible<value_type>::value && is_trivially_copy_assignable<value_type>::value ? 30 : 6;
+  while (true) {
+  __restart:
+    difference_type __len = __last - __first;
+    switch (__len) {
     case 0:
     case 1:
-        return true;
+      return;
     case 2:
-        if (__comp(*--__last, *__first))
-            swap(*__first, *__last);
-        return true;
+      if (__comp(*--__last, *__first))
+        swap(*__first, *__last);
+      return;
     case 3:
-        _VSTD::__sort3<_Compare>(__first, __first+difference_type(1), --__last, __comp);
-        return true;
+      _VSTD::__sort3_maybe_branchless<_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 true;
+      _VSTD::__sort4_maybe_branchless<_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 true;
+      _VSTD::__sort5_maybe_branchless<_Compare>(__first, __first + difference_type(1), __first + difference_type(2),
+                                                __first + difference_type(3), --__last, __comp);
+      return;
     }
-    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);
-    const unsigned __limit = 8;
-    unsigned __count = 0;
-    for (_RandomAccessIterator __i = __j+difference_type(1); __i != __last; ++__i)
-    {
-        if (__comp(*__i, *__j))
-        {
-            value_type __t(_VSTD::move(*__i));
-            _RandomAccessIterator __k = __j;
-            __j = __i;
-            do
-            {
-                *__j = _VSTD::move(*__k);
-                __j = __k;
-            } while (__j != __first && __comp(__t, *--__k));
-            *__j = _VSTD::move(__t);
-            if (++__count == __limit)
-                return ++__i == __last;
-        }
-        __j = __i;
+    if (__len <= __limit) {
+      _VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp);
+      return;
     }
-    return true;
-}
-
-template <class _Compare, class _BidirectionalIterator>
-void
-__insertion_sort_move(_BidirectionalIterator __first1, _BidirectionalIterator __last1,
-                      typename iterator_traits<_BidirectionalIterator>::value_type* __first2, _Compare __comp)
-{
-    typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
-    if (__first1 != __last1)
+    // __len > 5
+    if (__depth == 0) {
+      // Fallback to heap sort as Introsort suggests.
+      _VSTD::__partial_sort<_Compare>(__first, __last, __last, __comp);
+      return;
+    }
+    --__depth;
+    _RandomAccessIterator __m = __first;
+    _RandomAccessIterator __lm1 = __last;
+    --__lm1;
+    unsigned __n_swaps;
     {
-        __destruct_n __d(0);
-        unique_ptr<value_type, __destruct_n&> __h(__first2, __d);
-        value_type* __last2 = __first2;
-        ::new ((void*)__last2) value_type(_VSTD::move(*__first1));
-        __d.template __incr<value_type>();
-        for (++__last2; ++__first1 != __last1; ++__last2)
-        {
-            value_type* __j2 = __last2;
-            value_type* __i2 = __j2;
-            if (__comp(*__first1, *--__i2))
-            {
-                ::new ((void*)__j2) value_type(_VSTD::move(*__i2));
-                __d.template __incr<value_type>();
-                for (--__j2; __i2 != __first2 && __comp(*__first1,  *--__i2); --__j2)
-                    *__j2 = _VSTD::move(*__i2);
-                *__j2 = _VSTD::move(*__first1);
-            }
-            else
-            {
-                ::new ((void*)__j2) value_type(_VSTD::move(*__first1));
-                __d.template __incr<value_type>();
-            }
-        }
-        __h.release();
+      difference_type __delta;
+      if (__len >= 1000) {
+        __delta = __len / 2;
+        __m += __delta;
+        __delta /= 2;
+        __n_swaps = _VSTD::__sort5<_Compare>(__first, __first + __delta, __m, __m + __delta, __lm1, __comp);
+      } else {
+        __delta = __len / 2;
+        __m += __delta;
+        __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, __lm1, __comp);
+      }
     }
-}
-
-template <class _Compare, class _RandomAccessIterator>
-void
-__introsort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
-            typename iterator_traits<_RandomAccessIterator>::difference_type __depth)
-{
-    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
-    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
-    const difference_type __limit = is_trivially_copy_constructible<value_type>::value &&
-                                    is_trivially_copy_assignable<value_type>::value ? 30 : 6;
-    while (true)
+    // *__m is median
+    // partition [__first, __m) < *__m and *__m <= [__m, __last)
+    // (this inhibits tossing elements equivalent to __m around unnecessarily)
+    _RandomAccessIterator __i = __first;
+    _RandomAccessIterator __j = __lm1;
+    // j points beyond range to be tested, *__m is known to be <= *__lm1
+    // The search going up is known to be guarded but the search coming down isn't.
+    // Prime the downward search with a guard.
+    if (!__comp(*__i, *__m)) // if *__first == *__m
     {
-    __restart:
-        difference_type __len = __last - __first;
-        switch (__len)
-        {
-        case 0:
-        case 1:
-            return;
-        case 2:
-            if (__comp(*--__last, *__first))
-                swap(*__first, *__last);
-            return;
-        case 3:
-            _VSTD::__sort3<_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;
-        case 5:
-            _VSTD::__sort5<_Compare>(__first, __first+difference_type(1), __first+difference_type(2), __first+difference_type(3), --__last, __comp);
-            return;
-        }
-        if (__len <= __limit)
-        {
-            _VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp);
-            return;
-        }
-        // __len > 5
-        if (__depth == 0)
-        {
-          // Fallback to heap sort as Introsort suggests.
-          _VSTD::__partial_sort<_Compare>(__first, __last, __last, __comp);
-          return;
-        }
-        --__depth;
-        _RandomAccessIterator __m = __first;
-        _RandomAccessIterator __lm1 = __last;
-        --__lm1;
-        unsigned __n_swaps;
-        {
-        difference_type __delta;
-        if (__len >= 1000)
-        {
-            __delta = __len/2;
-            __m += __delta;
-            __delta /= 2;
-            __n_swaps = _VSTD::__sort5<_Compare>(__first, __first + __delta, __m, __m+__delta, __lm1, __comp);
-        }
-        else
-        {
-            __delta = __len/2;
-            __m += __delta;
-            __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, __lm1, __comp);
-        }
-        }
-        // *__m is median
-        // partition [__first, __m) < *__m and *__m <= [__m, __last)
-        // (this inhibits tossing elements equivalent to __m around unnecessarily)
-        _RandomAccessIterator __i = __first;
-        _RandomAccessIterator __j = __lm1;
-        // j points beyond range to be tested, *__m is known to be <= *__lm1
-        // The search going up is known to be guarded but the search coming down isn't.
-        // Prime the downward search with a guard.
-        if (!__comp(*__i, *__m))  // if *__first == *__m
-        {
-            // *__first == *__m, *__first doesn't go in first part
-            // manually guard downward moving __j against __i
-            while (true)
-            {
-                if (__i == --__j)
-                {
-                    // *__first == *__m, *__m <= all other elements
-                    // Parition instead into [__first, __i) == *__first and *__first < [__i, __last)
-                    ++__i;  // __first + 1
-                    __j = __last;
-                    if (!__comp(*__first, *--__j))  // we need a guard if *__first == *(__last-1)
-                    {
-                        while (true)
-                        {
-                            if (__i == __j)
-                                return;  // [__first, __last) all equivalent elements
-                            if (__comp(*__first, *__i))
-                            {
-                                swap(*__i, *__j);
-                                ++__n_swaps;
-                                ++__i;
-                                break;
-                            }
-                            ++__i;
-                        }
-                    }
-                    // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
-                    if (__i == __j)
-                        return;
-                    while (true)
-                    {
-                        while (!__comp(*__first, *__i))
-                            ++__i;
-                        while (__comp(*__first, *--__j))
-                            ;
-                        if (__i >= __j)
-                            break;
-                        swap(*__i, *__j);
-                        ++__n_swaps;
-                        ++__i;
-                    }
-                    // [__first, __i) == *__first and *__first < [__i, __last)
-                    // The first part is sorted, sort the second part
-                    // _VSTD::__sort<_Compare>(__i, __last, __comp);
-                    __first = __i;
-                    goto __restart;
-                }
-                if (__comp(*__j, *__m))
-                {
-                    swap(*__i, *__j);
-                    ++__n_swaps;
-                    break;  // found guard for downward moving __j, now use unguarded partition
-                }
-            }
-        }
-        // It is known that *__i < *__m
-        ++__i;
-        // j points beyond range to be tested, *__m is known to be <= *__lm1
-        // if not yet partitioned...
-        if (__i < __j)
-        {
-            // known that *(__i - 1) < *__m
-            // known that __i <= __m
-            while (true)
-            {
-                // __m still guards upward moving __i
-                while (__comp(*__i, *__m))
-                    ++__i;
-                // It is now known that a guard exists for downward moving __j
-                while (!__comp(*--__j, *__m))
-                    ;
-                if (__i > __j)
-                    break;
+      // *__first == *__m, *__first doesn't go in first part
+      // manually guard downward moving __j against __i
+      while (true) {
+        if (__i == --__j) {
+          // *__first == *__m, *__m <= all other elements
+          // Parition instead into [__first, __i) == *__first and *__first < [__i, __last)
+          ++__i; // __first + 1
+          __j = __last;
+          if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1)
+          {
+            while (true) {
+              if (__i == __j)
+                return; // [__first, __last) all equivalent elements
+              if (__comp(*__first, *__i)) {
                 swap(*__i, *__j);
                 ++__n_swaps;
-                // It is known that __m != __j
-                // If __m just moved, follow it
-                if (__m == __i)
-                    __m = __j;
                 ++__i;
+                break;
+              }
+              ++__i;
             }
-        }
-        // [__first, __i) < *__m and *__m <= [__i, __last)
-        if (__i != __m && __comp(*__m, *__i))
-        {
-            swap(*__i, *__m);
+          }
+          // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
+          if (__i == __j)
+            return;
+          while (true) {
+            while (!__comp(*__first, *__i))
+              ++__i;
+            while (__comp(*__first, *--__j))
+              ;
+            if (__i >= __j)
+              break;
+            swap(*__i, *__j);
             ++__n_swaps;
+            ++__i;
+          }
+          // [__first, __i) == *__first and *__first < [__i, __last)
+          // The first part is sorted, sort the second part
+          // _VSTD::__sort<_Compare>(__i, __last, __comp);
+          __first = __i;
+          goto __restart;
         }
-        // [__first, __i) < *__i and *__i <= [__i+1, __last)
-        // If we were given a perfect partition, see if insertion sort is quick...
-        if (__n_swaps == 0)
-        {
-            bool __fs = _VSTD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp);
-            if (_VSTD::__insertion_sort_incomplete<_Compare>(__i+difference_type(1), __last, __comp))
-            {
-                if (__fs)
-                    return;
-                __last = __i;
-                continue;
-            }
-            else
-            {
-                if (__fs)
-                {
-                    __first = ++__i;
-                    continue;
-                }
-            }
+        if (__comp(*__j, *__m)) {
+          swap(*__i, *__j);
+          ++__n_swaps;
+          break; // found guard for downward moving __j, now use unguarded partition
         }
-        // sort smaller range with recursive call and larger with tail recursion elimination
-        if (__i - __first < __last - __i)
-        {
-          _VSTD::__introsort<_Compare>(__first, __i, __comp, __depth);
+      }
+    }
+    // It is known that *__i < *__m
+    ++__i;
+    // j points beyond range to be tested, *__m is known to be <= *__lm1
+    // if not yet partitioned...
+    if (__i < __j) {
+      // known that *(__i - 1) < *__m
+      // known that __i <= __m
+      while (true) {
+        // __m still guards upward moving __i
+        while (__comp(*__i, *__m))
+          ++__i;
+        // It is now known that a guard exists for downward moving __j
+        while (!__comp(*--__j, *__m))
+          ;
+        if (__i > __j)
+          break;
+        swap(*__i, *__j);
+        ++__n_swaps;
+        // It is known that __m != __j
+        // If __m just moved, follow it
+        if (__m == __i)
+          __m = __j;
+        ++__i;
+      }
+    }
+    // [__first, __i) < *__m and *__m <= [__i, __last)
+    if (__i != __m && __comp(*__m, *__i)) {
+      swap(*__i, *__m);
+      ++__n_swaps;
+    }
+    // [__first, __i) < *__i and *__i <= [__i+1, __last)
+    // If we were given a perfect partition, see if insertion sort is quick...
+    if (__n_swaps == 0) {
+      bool __fs = _VSTD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp);
+      if (_VSTD::__insertion_sort_incomplete<_Compare>(__i + difference_type(1), __last, __comp)) {
+        if (__fs)
+          return;
+        __last = __i;
+        continue;
+      } else {
+        if (__fs) {
           __first = ++__i;
+          continue;
         }
-        else
-        {
-          _VSTD::__introsort<_Compare>(__i + difference_type(1), __last, __comp, __depth);
-          __last = __i;
-        }
+      }
+    }
+    // sort smaller range with recursive call and larger with tail recursion elimination
+    if (__i - __first < __last - __i) {
+      _VSTD::__introsort<_Compare>(__first, __i, __comp, __depth);
+      __first = ++__i;
+    } else {
+      _VSTD::__introsort<_Compare>(__i + difference_type(1), __last, __comp, __depth);
+      __last = __i;
     }
+  }
 }
 
 template <typename _Number>
@@ -483,12 +514,9 @@ void __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compar
 }
 
 template <class _Compare, class _Tp>
-inline _LIBCPP_INLINE_VISIBILITY
-void
-__sort(_Tp** __first, _Tp** __last, __less<_Tp*>&)
-{
-    __less<uintptr_t> __comp;
-    _VSTD::__sort<__less<uintptr_t>&, uintptr_t*>((uintptr_t*)__first, (uintptr_t*)__last, __comp);
+inline _LIBCPP_INLINE_VISIBILITY void __sort(_Tp** __first, _Tp** __last, __less<_Tp*>&) {
+  __less<uintptr_t> __comp;
+  _VSTD::__sort<__less<uintptr_t>&, uintptr_t*>((uintptr_t*)__first, (uintptr_t*)__last, __comp);
 }
 
 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<char>&, char*>(char*, char*, __less<char>&))
@@ -530,10 +558,8 @@ _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less
 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS unsigned __sort5<__less<long double>&, long double*>(long double*, long double*, long double*, long double*, long double*, __less<long double>&))
 
 template <class _RandomAccessIterator, class _Compare>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-void
-sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
-{
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 void
+sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
   _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __last);
   typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
   if (__libcpp_is_constant_evaluated()) {
@@ -544,11 +570,9 @@ sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __com
 }
 
 template <class _RandomAccessIterator>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-void
-sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
-{
-    _VSTD::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 void sort(_RandomAccessIterator __first,
+                                                                         _RandomAccessIterator __last) {
+  _VSTD::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
 }
 
 _LIBCPP_END_NAMESPACE_STD