libcxx/include/__algorithm/sort.h

   1 //===----------------------------------------------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #ifndef _LIBCPP___ALGORITHM_SORT_H
  10 #define _LIBCPP___ALGORITHM_SORT_H
  11
  12 #include <__algorithm/comp.h>
  13 #include <__algorithm/comp_ref_type.h>
  14 #include <__algorithm/iter_swap.h>
  15 #include <__algorithm/iterator_operations.h>
  16 #include <__algorithm/min_element.h>
  17 #include <__algorithm/partial_sort.h>
  18 #include <__algorithm/unwrap_iter.h>
  19 #include <__assert>
  20 #include <__bit/blsr.h>
  21 #include <__bit/countl.h>
  22 #include <__bit/countr.h>
  23 #include <__config>
  24 #include <__debug_utils/randomize_range.h>
  25 #include <__debug_utils/strict_weak_ordering_check.h>
  26 #include <__functional/operations.h>
  27 #include <__functional/ranges_operations.h>
  28 #include <__iterator/iterator_traits.h>
  29 #include <__type_traits/conditional.h>
  30 #include <__type_traits/disjunction.h>
  31 #include <__type_traits/is_arithmetic.h>
  32 #include <__type_traits/is_constant_evaluated.h>
  33 #include <__utility/move.h>
  34 #include <__utility/pair.h>
  35 #include <climits>
  36 #include <cstdint>
  37
  38 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
  39 #  pragma GCC system_header
  40 #endif
  41
  42 _LIBCPP_BEGIN_NAMESPACE_STD
  43
  44 // stable, 2-3 compares, 0-2 swaps
  45
  46 template <class _AlgPolicy, class _Compare, class _ForwardIterator>
  47 _LIBCPP_HIDE_FROM_ABI
  48 _LIBCPP_CONSTEXPR_SINCE_CXX14 unsigned __sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z,
  49                                                _Compare __c) {
  50   using _Ops = _IterOps<_AlgPolicy>;
  51
  52   unsigned __r = 0;
  53   if (!__c(*__y, *__x))   // if x <= y
  54   {
  55     if (!__c(*__z, *__y)) // if y <= z
  56       return __r;         // x <= y && y <= z
  57                           // x <= y && y > z
  58     _Ops::iter_swap(__y, __z);     // x <= z && y < z
  59     __r = 1;
  60     if (__c(*__y, *__x))  // if x > y
  61     {
  62       _Ops::iter_swap(__x, __y);   // x < y && y <= z
  63       __r = 2;
  64     }
  65     return __r;           // x <= y && y < z
  66   }
  67   if (__c(*__z, *__y))    // x > y, if y > z
  68   {
  69     _Ops::iter_swap(__x, __z);     // x < y && y < z
  70     __r = 1;
  71     return __r;
  72   }
  73   _Ops::iter_swap(__x, __y);       // x > y && y <= z
  74   __r = 1;                // x < y && x <= z
  75   if (__c(*__z, *__y))    // if y > z
  76   {
  77     _Ops::iter_swap(__y, __z);     // x <= y && y < z
  78     __r = 2;
  79   }
  80   return __r;
  81 }                         // x <= y && y <= z
  82
  83 // stable, 3-6 compares, 0-5 swaps
  84
  85 template <class _AlgPolicy, class _Compare, class _ForwardIterator>
  86 _LIBCPP_HIDE_FROM_ABI
  87 void __sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, _ForwardIterator __x4,
  88                  _Compare __c) {
  89   using _Ops   = _IterOps<_AlgPolicy>;
  90   std::__sort3<_AlgPolicy, _Compare>(__x1, __x2, __x3, __c);
  91   if (__c(*__x4, *__x3)) {
  92     _Ops::iter_swap(__x3, __x4);
  93     if (__c(*__x3, *__x2)) {
  94       _Ops::iter_swap(__x2, __x3);
  95       if (__c(*__x2, *__x1)) {
  96         _Ops::iter_swap(__x1, __x2);
  97       }
  98     }
  99   }
 100 }
 101
 102 // stable, 4-10 compares, 0-9 swaps
 103
 104 template <class _AlgPolicy, class _Comp, class _ForwardIterator>
 105 _LIBCPP_HIDE_FROM_ABI void __sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
 106                                    _ForwardIterator __x4, _ForwardIterator __x5, _Comp __comp) {
 107   using _Ops = _IterOps<_AlgPolicy>;
 108
 109   std::__sort4<_AlgPolicy, _Comp>(__x1, __x2, __x3, __x4, __comp);
 110   if (__comp(*__x5, *__x4)) {
 111     _Ops::iter_swap(__x4, __x5);
 112     if (__comp(*__x4, *__x3)) {
 113       _Ops::iter_swap(__x3, __x4);
 114       if (__comp(*__x3, *__x2)) {
 115         _Ops::iter_swap(__x2, __x3);
 116         if (__comp(*__x2, *__x1)) {
 117           _Ops::iter_swap(__x1, __x2);
 118         }
 119       }
 120     }
 121   }
 122 }
 123
 124 // The comparator being simple is a prerequisite for using the branchless optimization.
 125 template <class _Tp>
 126 struct __is_simple_comparator : false_type {};
 127 template <>
 128 struct __is_simple_comparator<__less<>&> : true_type {};
 129 template <class _Tp>
 130 struct __is_simple_comparator<less<_Tp>&> : true_type {};
 131 template <class _Tp>
 132 struct __is_simple_comparator<greater<_Tp>&> : true_type {};
 133 #if _LIBCPP_STD_VER >= 20
 134 template <>
 135 struct __is_simple_comparator<ranges::less&> : true_type {};
 136 template <>
 137 struct __is_simple_comparator<ranges::greater&> : true_type {};
 138 #endif
 139
 140 template <class _Compare, class _Iter, class _Tp = typename iterator_traits<_Iter>::value_type>
 141 using __use_branchless_sort =
 142     integral_constant<bool, __libcpp_is_contiguous_iterator<_Iter>::value && sizeof(_Tp) <= sizeof(void*) &&
 143                                 is_arithmetic<_Tp>::value && __is_simple_comparator<_Compare>::value>;
 144
 145 namespace __detail {
 146
 147 // Size in bits for the bitset in use.
 148 enum { __block_size = sizeof(uint64_t) * 8 };
 149
 150 } // namespace __detail
 151
 152 // Ensures that __c(*__x, *__y) is true by swapping *__x and *__y if necessary.
 153 template <class _Compare, class _RandomAccessIterator>
 154 inline _LIBCPP_HIDE_FROM_ABI void __cond_swap(_RandomAccessIterator __x, _RandomAccessIterator __y, _Compare __c) {
 155   // Note: this function behaves correctly even with proxy iterators (because it relies on `value_type`).
 156   using value_type = typename iterator_traits<_RandomAccessIterator>::value_type;
 157   bool __r = __c(*__x, *__y);
 158   value_type __tmp = __r ? *__x : *__y;
 159   *__y = __r ? *__y : *__x;
 160   *__x = __tmp;
 161 }
 162
 163 // Ensures that *__x, *__y and *__z are ordered according to the comparator __c,
 164 // under the assumption that *__y and *__z are already ordered.
 165 template <class _Compare, class _RandomAccessIterator>
 166 inline _LIBCPP_HIDE_FROM_ABI void __partially_sorted_swap(_RandomAccessIterator __x, _RandomAccessIterator __y,
 167                                                           _RandomAccessIterator __z, _Compare __c) {
 168   // Note: this function behaves correctly even with proxy iterators (because it relies on `value_type`).
 169   using value_type = typename iterator_traits<_RandomAccessIterator>::value_type;
 170   bool __r = __c(*__z, *__x);
 171   value_type __tmp = __r ? *__z : *__x;
 172   *__z = __r ? *__x : *__z;
 173   __r = __c(__tmp, *__y);
 174   *__x = __r ? *__x : *__y;
 175   *__y = __r ? *__y : __tmp;
 176 }
 177
 178 template <class, class _Compare, class _RandomAccessIterator,
 179           __enable_if_t<__use_branchless_sort<_Compare, _RandomAccessIterator>::value, int> = 0>
 180 inline _LIBCPP_HIDE_FROM_ABI void
 181 __sort3_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3,
 182                          _Compare __c) {
 183   std::__cond_swap<_Compare>(__x2, __x3, __c);
 184   std::__partially_sorted_swap<_Compare>(__x1, __x2, __x3, __c);
 185 }
 186
 187 template <class _AlgPolicy, class _Compare, class _RandomAccessIterator,
 188           __enable_if_t<!__use_branchless_sort<_Compare, _RandomAccessIterator>::value, int> = 0>
 189 inline _LIBCPP_HIDE_FROM_ABI void
 190 __sort3_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3,
 191                          _Compare __c) {
 192   std::__sort3<_AlgPolicy, _Compare>(__x1, __x2, __x3, __c);
 193 }
 194
 195 template <class, class _Compare, class _RandomAccessIterator,
 196           __enable_if_t<__use_branchless_sort<_Compare, _RandomAccessIterator>::value, int> = 0>
 197 inline _LIBCPP_HIDE_FROM_ABI void
 198 __sort4_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3,
 199                          _RandomAccessIterator __x4, _Compare __c) {
 200   std::__cond_swap<_Compare>(__x1, __x3, __c);
 201   std::__cond_swap<_Compare>(__x2, __x4, __c);
 202   std::__cond_swap<_Compare>(__x1, __x2, __c);
 203   std::__cond_swap<_Compare>(__x3, __x4, __c);
 204   std::__cond_swap<_Compare>(__x2, __x3, __c);
 205 }
 206
 207 template <class _AlgPolicy, class _Compare, class _RandomAccessIterator,
 208           __enable_if_t<!__use_branchless_sort<_Compare, _RandomAccessIterator>::value, int> = 0>
 209 inline _LIBCPP_HIDE_FROM_ABI void
 210 __sort4_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3,
 211                          _RandomAccessIterator __x4, _Compare __c) {
 212   std::__sort4<_AlgPolicy, _Compare>(__x1, __x2, __x3, __x4, __c);
 213 }
 214
 215 template <class _AlgPolicy, class _Compare, class _RandomAccessIterator,
 216           __enable_if_t<__use_branchless_sort<_Compare, _RandomAccessIterator>::value, int> = 0>
 217 inline _LIBCPP_HIDE_FROM_ABI void
 218 __sort5_maybe_branchless(
 219     _RandomAccessIterator __x1,
 220     _RandomAccessIterator __x2,
 221     _RandomAccessIterator __x3,
 222     _RandomAccessIterator __x4,
 223     _RandomAccessIterator __x5,
 224     _Compare __c) {
 225   std::__cond_swap<_Compare>(__x1, __x2, __c);
 226   std::__cond_swap<_Compare>(__x4, __x5, __c);
 227   std::__partially_sorted_swap<_Compare>(__x3, __x4, __x5, __c);
 228   std::__cond_swap<_Compare>(__x2, __x5, __c);
 229   std::__partially_sorted_swap<_Compare>(__x1, __x3, __x4, __c);
 230   std::__partially_sorted_swap<_Compare>(__x2, __x3, __x4, __c);
 231 }
 232
 233 template <class _AlgPolicy, class _Compare, class _RandomAccessIterator,
 234           __enable_if_t<!__use_branchless_sort<_Compare, _RandomAccessIterator>::value, int> = 0>
 235 inline _LIBCPP_HIDE_FROM_ABI void
 236 __sort5_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3,
 237                          _RandomAccessIterator __x4, _RandomAccessIterator __x5, _Compare __c) {
 238   std::__sort5<_AlgPolicy, _Compare, _RandomAccessIterator>(
 239       std::move(__x1), std::move(__x2), std::move(__x3), std::move(__x4), std::move(__x5), __c);
 240 }
 241
 242 // Assumes size > 0
 243 template <class _AlgPolicy, class _Compare, class _BidirectionalIterator>
 244 _LIBCPP_HIDE_FROM_ABI
 245 _LIBCPP_CONSTEXPR_SINCE_CXX14 void __selection_sort(_BidirectionalIterator __first, _BidirectionalIterator __last,
 246                                                     _Compare __comp) {
 247   _BidirectionalIterator __lm1 = __last;
 248   for (--__lm1; __first != __lm1; ++__first) {
 249     _BidirectionalIterator __i = std::__min_element<_Compare>(__first, __last, __comp);
 250     if (__i != __first)
 251       _IterOps<_AlgPolicy>::iter_swap(__first, __i);
 252   }
 253 }
 254
 255 // Sort the iterator range [__first, __last) using the comparator __comp using
 256 // the insertion sort algorithm.
 257 template <class _AlgPolicy, class _Compare, class _BidirectionalIterator>
 258 _LIBCPP_HIDE_FROM_ABI
 259 void __insertion_sort(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) {
 260   using _Ops = _IterOps<_AlgPolicy>;
 261
 262   typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
 263   if (__first == __last)
 264     return;
 265   _BidirectionalIterator __i = __first;
 266   for (++__i; __i != __last; ++__i) {
 267     _BidirectionalIterator __j = __i;
 268     --__j;
 269     if (__comp(*__i, *__j)) {
 270       value_type __t(_Ops::__iter_move(__i));
 271       _BidirectionalIterator __k = __j;
 272       __j                        = __i;
 273       do {
 274         *__j = _Ops::__iter_move(__k);
 275         __j  = __k;
 276       } while (__j != __first && __comp(__t, *--__k));
 277       *__j = std::move(__t);
 278     }
 279   }
 280 }
 281
 282 // Sort the iterator range [__first, __last) using the comparator __comp using
 283 // the insertion sort algorithm.  Insertion sort has two loops, outer and inner.
 284 // The implementation below has no bounds check (unguarded) for the inner loop.
 285 // Assumes that there is an element in the position (__first - 1) and that each
 286 // element in the input range is greater or equal to the element at __first - 1.
 287 template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
 288 _LIBCPP_HIDE_FROM_ABI void
 289 __insertion_sort_unguarded(_RandomAccessIterator const __first, _RandomAccessIterator __last, _Compare __comp) {
 290   using _Ops = _IterOps<_AlgPolicy>;
 291   typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
 292   typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
 293   if (__first == __last)
 294     return;
 295   const _RandomAccessIterator __leftmost = __first - difference_type(1); (void)__leftmost; // can be unused when assertions are disabled
 296   for (_RandomAccessIterator __i = __first + difference_type(1); __i != __last; ++__i) {
 297     _RandomAccessIterator __j = __i - difference_type(1);
 298     if (__comp(*__i, *__j)) {
 299       value_type __t(_Ops::__iter_move(__i));
 300       _RandomAccessIterator __k = __j;
 301       __j = __i;
 302       do {
 303         *__j = _Ops::__iter_move(__k);
 304         __j = __k;
 305         _LIBCPP_ASSERT_UNCATEGORIZED(
 306             __k != __leftmost,
 307             "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?");
 308       } while (__comp(__t, *--__k)); // No need for bounds check due to the assumption stated above.
 309       *__j = std::move(__t);
 310     }
 311   }
 312 }
 313
 314 template <class _AlgPolicy, class _Comp, class _RandomAccessIterator>
 315 _LIBCPP_HIDE_FROM_ABI bool __insertion_sort_incomplete(
 316     _RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp) {
 317   using _Ops = _IterOps<_AlgPolicy>;
 318
 319   typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
 320   switch (__last - __first) {
 321   case 0:
 322   case 1:
 323     return true;
 324   case 2:
 325     if (__comp(*--__last, *__first))
 326       _Ops::iter_swap(__first, __last);
 327     return true;
 328   case 3:
 329     std::__sort3_maybe_branchless<_AlgPolicy, _Comp>(__first, __first + difference_type(1), --__last, __comp);
 330     return true;
 331   case 4:
 332     std::__sort4_maybe_branchless<_AlgPolicy, _Comp>(
 333         __first, __first + difference_type(1), __first + difference_type(2), --__last, __comp);
 334     return true;
 335   case 5:
 336     std::__sort5_maybe_branchless<_AlgPolicy, _Comp>(
 337         __first, __first + difference_type(1), __first + difference_type(2), __first + difference_type(3),
 338         --__last, __comp);
 339     return true;
 340   }
 341   typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
 342   _RandomAccessIterator __j = __first + difference_type(2);
 343   std::__sort3_maybe_branchless<_AlgPolicy, _Comp>(__first, __first + difference_type(1), __j, __comp);
 344   const unsigned __limit = 8;
 345   unsigned __count = 0;
 346   for (_RandomAccessIterator __i = __j + difference_type(1); __i != __last; ++__i) {
 347     if (__comp(*__i, *__j)) {
 348       value_type __t(_Ops::__iter_move(__i));
 349       _RandomAccessIterator __k = __j;
 350       __j = __i;
 351       do {
 352         *__j = _Ops::__iter_move(__k);
 353         __j = __k;
 354       } while (__j != __first && __comp(__t, *--__k));
 355       *__j = std::move(__t);
 356       if (++__count == __limit)
 357         return ++__i == __last;
 358     }
 359     __j = __i;
 360   }
 361   return true;
 362 }
 363
 364 template <class _AlgPolicy, class _RandomAccessIterator>
 365 inline _LIBCPP_HIDE_FROM_ABI void __swap_bitmap_pos(
 366     _RandomAccessIterator __first, _RandomAccessIterator __last, uint64_t& __left_bitset, uint64_t& __right_bitset) {
 367   using _Ops = _IterOps<_AlgPolicy>;
 368   typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type difference_type;
 369   // Swap one pair on each iteration as long as both bitsets have at least one
 370   // element for swapping.
 371   while (__left_bitset != 0 && __right_bitset != 0) {
 372     difference_type __tz_left  = __libcpp_ctz(__left_bitset);
 373     __left_bitset              = __libcpp_blsr(__left_bitset);
 374     difference_type __tz_right = __libcpp_ctz(__right_bitset);
 375     __right_bitset             = __libcpp_blsr(__right_bitset);
 376     _Ops::iter_swap(__first + __tz_left, __last - __tz_right);
 377   }
 378 }
 379
 380 template <class _Compare,
 381           class _RandomAccessIterator,
 382           class _ValueType = typename iterator_traits<_RandomAccessIterator>::value_type>
 383 inline _LIBCPP_HIDE_FROM_ABI void
 384 __populate_left_bitset(_RandomAccessIterator __first, _Compare __comp, _ValueType& __pivot, uint64_t& __left_bitset) {
 385   // Possible vectorization. With a proper "-march" flag, the following loop
 386   // will be compiled into a set of SIMD instructions.
 387   _RandomAccessIterator __iter = __first;
 388   for (int __j = 0; __j < __detail::__block_size;) {
 389     bool __comp_result = !__comp(*__iter, __pivot);
 390     __left_bitset |= (static_cast<uint64_t>(__comp_result) << __j);
 391     __j++;
 392     ++__iter;
 393   }
 394 }
 395
 396 template <class _Compare,
 397           class _RandomAccessIterator,
 398           class _ValueType = typename iterator_traits<_RandomAccessIterator>::value_type>
 399 inline _LIBCPP_HIDE_FROM_ABI void
 400 __populate_right_bitset(_RandomAccessIterator __lm1, _Compare __comp, _ValueType& __pivot, uint64_t& __right_bitset) {
 401   // Possible vectorization. With a proper "-march" flag, the following loop
 402   // will be compiled into a set of SIMD instructions.
 403   _RandomAccessIterator __iter = __lm1;
 404   for (int __j = 0; __j < __detail::__block_size;) {
 405     bool __comp_result = __comp(*__iter, __pivot);
 406     __right_bitset |= (static_cast<uint64_t>(__comp_result) << __j);
 407     __j++;
 408     --__iter;
 409   }
 410 }
 411
 412 template <class _AlgPolicy,
 413           class _Compare,
 414           class _RandomAccessIterator,
 415           class _ValueType = typename iterator_traits<_RandomAccessIterator>::value_type>
 416 inline _LIBCPP_HIDE_FROM_ABI void __bitset_partition_partial_blocks(
 417     _RandomAccessIterator& __first,
 418     _RandomAccessIterator& __lm1,
 419     _Compare __comp,
 420     _ValueType& __pivot,
 421     uint64_t& __left_bitset,
 422     uint64_t& __right_bitset) {
 423   typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type difference_type;
 424   difference_type __remaining_len = __lm1 - __first + 1;
 425   difference_type __l_size;
 426   difference_type __r_size;
 427   if (__left_bitset == 0 && __right_bitset == 0) {
 428     __l_size = __remaining_len / 2;
 429     __r_size = __remaining_len - __l_size;
 430   } else if (__left_bitset == 0) {
 431     // We know at least one side is a full block.
 432     __l_size = __remaining_len - __detail::__block_size;
 433     __r_size = __detail::__block_size;
 434   } else { // if (__right_bitset == 0)
 435     __l_size = __detail::__block_size;
 436     __r_size = __remaining_len - __detail::__block_size;
 437   }
 438   // Record the comparison outcomes for the elements currently on the left side.
 439   if (__left_bitset == 0) {
 440     _RandomAccessIterator __iter = __first;
 441     for (int __j = 0; __j < __l_size; __j++) {
 442       bool __comp_result = !__comp(*__iter, __pivot);
 443       __left_bitset |= (static_cast<uint64_t>(__comp_result) << __j);
 444       ++__iter;
 445     }
 446   }
 447   // Record the comparison outcomes for the elements currently on the right
 448   // side.
 449   if (__right_bitset == 0) {
 450     _RandomAccessIterator __iter = __lm1;
 451     for (int __j = 0; __j < __r_size; __j++) {
 452       bool __comp_result = __comp(*__iter, __pivot);
 453       __right_bitset |= (static_cast<uint64_t>(__comp_result) << __j);
 454       --__iter;
 455     }
 456   }
 457   std::__swap_bitmap_pos<_AlgPolicy, _RandomAccessIterator>(__first, __lm1, __left_bitset, __right_bitset);
 458   __first += (__left_bitset == 0) ? __l_size : 0;
 459   __lm1 -= (__right_bitset == 0) ? __r_size : 0;
 460 }
 461
 462 template <class _AlgPolicy, class _RandomAccessIterator>
 463 inline _LIBCPP_HIDE_FROM_ABI void __swap_bitmap_pos_within(
 464     _RandomAccessIterator& __first, _RandomAccessIterator& __lm1, uint64_t& __left_bitset, uint64_t& __right_bitset) {
 465   using _Ops = _IterOps<_AlgPolicy>;
 466   typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type difference_type;
 467   if (__left_bitset) {
 468     // Swap within the left side.  Need to find set positions in the reverse
 469     // order.
 470     while (__left_bitset != 0) {
 471       difference_type __tz_left = __detail::__block_size - 1 - __libcpp_clz(__left_bitset);
 472       __left_bitset &= (static_cast<uint64_t>(1) << __tz_left) - 1;
 473       _RandomAccessIterator __it = __first + __tz_left;
 474       if (__it != __lm1) {
 475         _Ops::iter_swap(__it, __lm1);
 476       }
 477       --__lm1;
 478     }
 479     __first = __lm1 + difference_type(1);
 480   } else if (__right_bitset) {
 481     // Swap within the right side.  Need to find set positions in the reverse
 482     // order.
 483     while (__right_bitset != 0) {
 484       difference_type __tz_right = __detail::__block_size - 1 - __libcpp_clz(__right_bitset);
 485       __right_bitset &= (static_cast<uint64_t>(1) << __tz_right) - 1;
 486       _RandomAccessIterator __it = __lm1 - __tz_right;
 487       if (__it != __first) {
 488         _Ops::iter_swap(__it, __first);
 489       }
 490       ++__first;
 491     }
 492   }
 493 }
 494
 495 // Partition [__first, __last) using the comparator __comp.  *__first has the
 496 // chosen pivot.  Elements that are equivalent are kept to the left of the
 497 // pivot.  Returns the iterator for the pivot and a bool value which is true if
 498 // the provided range is already sorted, false otherwise.  We assume that the
 499 // length of the range is at least three elements.
 500 //
 501 // __bitset_partition uses bitsets for storing outcomes of the comparisons
 502 // between the pivot and other elements.
 503 template <class _AlgPolicy, class _RandomAccessIterator, class _Compare>
 504 _LIBCPP_HIDE_FROM_ABI std::pair<_RandomAccessIterator, bool>
 505 __bitset_partition(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
 506   using _Ops = _IterOps<_AlgPolicy>;
 507   typedef typename std::iterator_traits<_RandomAccessIterator>::value_type value_type;
 508   typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type difference_type;
 509   _LIBCPP_ASSERT_UNCATEGORIZED(__last - __first >= difference_type(3), "");
 510   const _RandomAccessIterator __begin = __first;            // used for bounds checking, those are not moved around
 511   const _RandomAccessIterator __end = __last; (void)__end;  //
 512
 513   value_type __pivot(_Ops::__iter_move(__first));
 514   // Find the first element greater than the pivot.
 515   if (__comp(__pivot, *(__last - difference_type(1)))) {
 516     // Not guarded since we know the last element is greater than the pivot.
 517     do {
 518       ++__first;
 519       _LIBCPP_ASSERT_UNCATEGORIZED(
 520           __first != __end,
 521           "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?");
 522     } while (!__comp(__pivot, *__first));
 523   } else {
 524     while (++__first < __last && !__comp(__pivot, *__first)) {
 525     }
 526   }
 527   // Find the last element less than or equal to the pivot.
 528   if (__first < __last) {
 529     // It will be always guarded because __introsort will do the median-of-three
 530     // before calling this.
 531     do {
 532       _LIBCPP_ASSERT_UNCATEGORIZED(
 533           __last != __begin,
 534           "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?");
 535       --__last;
 536     } while (__comp(__pivot, *__last));
 537   }
 538   // If the first element greater than the pivot is at or after the
 539   // last element less than or equal to the pivot, then we have covered the
 540   // entire range without swapping elements.  This implies the range is already
 541   // partitioned.
 542   bool __already_partitioned = __first >= __last;
 543   if (!__already_partitioned) {
 544     _Ops::iter_swap(__first, __last);
 545     ++__first;
 546   }
 547
 548   // In [__first, __last) __last is not inclusive. From now on, it uses last
 549   // minus one to be inclusive on both sides.
 550   _RandomAccessIterator __lm1 = __last - difference_type(1);
 551   uint64_t __left_bitset      = 0;
 552   uint64_t __right_bitset     = 0;
 553
 554   // Reminder: length = __lm1 - __first + 1.
 555   while (__lm1 - __first >= 2 * __detail::__block_size - 1) {
 556     // Record the comparison outcomes for the elements currently on the left
 557     // side.
 558     if (__left_bitset == 0)
 559       std::__populate_left_bitset<_Compare>(__first, __comp, __pivot, __left_bitset);
 560     // Record the comparison outcomes for the elements currently on the right
 561     // side.
 562     if (__right_bitset == 0)
 563       std::__populate_right_bitset<_Compare>(__lm1, __comp, __pivot, __right_bitset);
 564     // Swap the elements recorded to be the candidates for swapping in the
 565     // bitsets.
 566     std::__swap_bitmap_pos<_AlgPolicy, _RandomAccessIterator>(__first, __lm1, __left_bitset, __right_bitset);
 567     // Only advance the iterator if all the elements that need to be moved to
 568     // other side were moved.
 569     __first += (__left_bitset == 0) ? difference_type(__detail::__block_size) : difference_type(0);
 570     __lm1 -= (__right_bitset == 0) ? difference_type(__detail::__block_size) : difference_type(0);
 571   }
 572   // Now, we have a less-than a block worth of elements on at least one of the
 573   // sides.
 574   std::__bitset_partition_partial_blocks<_AlgPolicy, _Compare>(
 575       __first, __lm1, __comp, __pivot, __left_bitset, __right_bitset);
 576   // At least one the bitsets would be empty.  For the non-empty one, we need to
 577   // properly partition the elements that appear within that bitset.
 578   std::__swap_bitmap_pos_within<_AlgPolicy>(__first, __lm1, __left_bitset, __right_bitset);
 579
 580   // Move the pivot to its correct position.
 581   _RandomAccessIterator __pivot_pos = __first - difference_type(1);
 582   if (__begin != __pivot_pos) {
 583     *__begin = _Ops::__iter_move(__pivot_pos);
 584   }
 585   *__pivot_pos = std::move(__pivot);
 586   return std::make_pair(__pivot_pos, __already_partitioned);
 587 }
 588
 589 // Partition [__first, __last) using the comparator __comp.  *__first has the
 590 // chosen pivot.  Elements that are equivalent are kept to the right of the
 591 // pivot.  Returns the iterator for the pivot and a bool value which is true if
 592 // the provided range is already sorted, false otherwise.  We assume that the
 593 // length of the range is at least three elements.
 594 template <class _AlgPolicy, class _RandomAccessIterator, class _Compare>
 595 _LIBCPP_HIDE_FROM_ABI std::pair<_RandomAccessIterator, bool>
 596 __partition_with_equals_on_right(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
 597   using _Ops = _IterOps<_AlgPolicy>;
 598   typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
 599   typedef typename std::iterator_traits<_RandomAccessIterator>::value_type value_type;
 600   _LIBCPP_ASSERT_UNCATEGORIZED(__last - __first >= difference_type(3), "");
 601   const _RandomAccessIterator __begin = __first;            // used for bounds checking, those are not moved around
 602   const _RandomAccessIterator __end = __last; (void)__end;  //
 603   value_type __pivot(_Ops::__iter_move(__first));
 604   // Find the first element greater or equal to the pivot.  It will be always
 605   // guarded because __introsort will do the median-of-three before calling
 606   // this.
 607   do {
 608     ++__first;
 609     _LIBCPP_ASSERT_UNCATEGORIZED(
 610         __first != __end,
 611         "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?");
 612   } while (__comp(*__first, __pivot));
 613
 614   // Find the last element less than the pivot.
 615   if (__begin == __first - difference_type(1)) {
 616     while (__first < __last && !__comp(*--__last, __pivot))
 617       ;
 618   } else {
 619     // Guarded.
 620     do {
 621       _LIBCPP_ASSERT_UNCATEGORIZED(
 622           __last != __begin,
 623           "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?");
 624       --__last;
 625     } while (!__comp(*__last, __pivot));
 626   }
 627
 628   // If the first element greater than or equal to the pivot is at or after the
 629   // last element less than the pivot, then we have covered the entire range
 630   // without swapping elements.  This implies the range is already partitioned.
 631   bool __already_partitioned = __first >= __last;
 632   // Go through the remaining elements.  Swap pairs of elements (one to the
 633   // right of the pivot and the other to left of the pivot) that are not on the
 634   // correct side of the pivot.
 635   while (__first < __last) {
 636     _Ops::iter_swap(__first, __last);
 637     do {
 638       ++__first;
 639       _LIBCPP_ASSERT_UNCATEGORIZED(
 640           __first != __end,
 641           "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?");
 642     } while (__comp(*__first, __pivot));
 643     do {
 644       _LIBCPP_ASSERT_UNCATEGORIZED(
 645           __last != __begin,
 646           "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?");
 647       --__last;
 648     } while (!__comp(*__last, __pivot));
 649   }
 650   // Move the pivot to its correct position.
 651   _RandomAccessIterator __pivot_pos = __first - difference_type(1);
 652   if (__begin != __pivot_pos) {
 653     *__begin = _Ops::__iter_move(__pivot_pos);
 654   }
 655   *__pivot_pos = std::move(__pivot);
 656   return std::make_pair(__pivot_pos, __already_partitioned);
 657 }
 658
 659 // Similar to the above function.  Elements equivalent to the pivot are put to
 660 // the left of the pivot.  Returns the iterator to the pivot element.
 661 template <class _AlgPolicy, class _RandomAccessIterator, class _Compare>
 662 _LIBCPP_HIDE_FROM_ABI _RandomAccessIterator
 663 __partition_with_equals_on_left(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
 664   using _Ops = _IterOps<_AlgPolicy>;
 665   typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
 666   typedef typename std::iterator_traits<_RandomAccessIterator>::value_type value_type;
 667   // TODO(LLVM18): Make __begin const, see https://reviews.llvm.org/D147089#4349748
 668   _RandomAccessIterator __begin = __first;                  // used for bounds checking, those are not moved around
 669   const _RandomAccessIterator __end = __last; (void)__end;  //
 670   value_type __pivot(_Ops::__iter_move(__first));
 671   if (__comp(__pivot, *(__last - difference_type(1)))) {
 672     // Guarded.
 673     do {
 674       ++__first;
 675       _LIBCPP_ASSERT_UNCATEGORIZED(
 676           __first != __end,
 677           "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?");
 678     } while (!__comp(__pivot, *__first));
 679   } else {
 680     while (++__first < __last && !__comp(__pivot, *__first)) {
 681     }
 682   }
 683
 684   if (__first < __last) {
 685     // It will be always guarded because __introsort will do the
 686     // median-of-three before calling this.
 687     do {
 688       _LIBCPP_ASSERT_UNCATEGORIZED(
 689           __last != __begin,
 690           "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?");
 691       --__last;
 692     } while (__comp(__pivot, *__last));
 693   }
 694   while (__first < __last) {
 695     _Ops::iter_swap(__first, __last);
 696     do {
 697       ++__first;
 698       _LIBCPP_ASSERT_UNCATEGORIZED(
 699           __first != __end,
 700           "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?");
 701     } while (!__comp(__pivot, *__first));
 702     do {
 703       _LIBCPP_ASSERT_UNCATEGORIZED(
 704           __last != __begin,
 705           "Would read out of bounds, does your comparator satisfy the strict-weak ordering requirement?");
 706       --__last;
 707     } while (__comp(__pivot, *__last));
 708   }
 709   _RandomAccessIterator __pivot_pos = __first - difference_type(1);
 710   if (__begin != __pivot_pos) {
 711     *__begin = _Ops::__iter_move(__pivot_pos);
 712   }
 713   *__pivot_pos = std::move(__pivot);
 714   return __first;
 715 }
 716
 717 // The main sorting function.  Implements introsort combined with other ideas:
 718 //  - option of using block quick sort for partitioning,
 719 //  - guarded and unguarded insertion sort for small lengths,
 720 //  - Tuckey's ninther technique for computing the pivot,
 721 //  - check on whether partition was not required.
 722 // The implementation is partly based on Orson Peters' pattern-defeating
 723 // quicksort, published at: <https://github.com/orlp/pdqsort>.
 724 template <class _AlgPolicy, class _Compare, class _RandomAccessIterator, bool _UseBitSetPartition>
 725 void __introsort(_RandomAccessIterator __first,
 726                  _RandomAccessIterator __last,
 727                  _Compare __comp,
 728                  typename iterator_traits<_RandomAccessIterator>::difference_type __depth,
 729                  bool __leftmost = true) {
 730   using _Ops = _IterOps<_AlgPolicy>;
 731   typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
 732   using _Comp_ref = __comp_ref_type<_Compare>;
 733   // Upper bound for using insertion sort for sorting.
 734   _LIBCPP_CONSTEXPR difference_type __limit = 24;
 735   // Lower bound for using Tuckey's ninther technique for median computation.
 736   _LIBCPP_CONSTEXPR difference_type __ninther_threshold = 128;
 737   while (true) {
 738     difference_type __len = __last - __first;
 739     switch (__len) {
 740     case 0:
 741     case 1:
 742       return;
 743     case 2:
 744       if (__comp(*--__last, *__first))
 745         _Ops::iter_swap(__first, __last);
 746       return;
 747     case 3:
 748       std::__sort3_maybe_branchless<_AlgPolicy, _Compare>(__first, __first + difference_type(1), --__last, __comp);
 749       return;
 750     case 4:
 751       std::__sort4_maybe_branchless<_AlgPolicy, _Compare>(
 752           __first, __first + difference_type(1), __first + difference_type(2), --__last, __comp);
 753       return;
 754     case 5:
 755       std::__sort5_maybe_branchless<_AlgPolicy, _Compare>(
 756           __first, __first + difference_type(1), __first + difference_type(2), __first + difference_type(3),
 757           --__last, __comp);
 758       return;
 759     }
 760     // Use insertion sort if the length of the range is below the specified limit.
 761     if (__len < __limit) {
 762       if (__leftmost) {
 763         std::__insertion_sort<_AlgPolicy, _Compare>(__first, __last, __comp);
 764       } else {
 765         std::__insertion_sort_unguarded<_AlgPolicy, _Compare>(__first, __last, __comp);
 766       }
 767       return;
 768     }
 769     if (__depth == 0) {
 770       // Fallback to heap sort as Introsort suggests.
 771       std::__partial_sort<_AlgPolicy, _Compare>(__first, __last, __last, __comp);
 772       return;
 773     }
 774     --__depth;
 775     {
 776       difference_type __half_len = __len / 2;
 777       // Use Tuckey's ninther technique or median of 3 for pivot selection
 778       // depending on the length of the range being sorted.
 779       if (__len > __ninther_threshold) {
 780         std::__sort3<_AlgPolicy, _Compare>(__first, __first + __half_len, __last - difference_type(1), __comp);
 781         std::__sort3<_AlgPolicy, _Compare>(
 782             __first + difference_type(1), __first + (__half_len - 1), __last - difference_type(2), __comp);
 783         std::__sort3<_AlgPolicy, _Compare>(
 784             __first + difference_type(2), __first + (__half_len + 1), __last - difference_type(3), __comp);
 785         std::__sort3<_AlgPolicy, _Compare>(
 786             __first + (__half_len - 1), __first + __half_len, __first + (__half_len + 1), __comp);
 787         _Ops::iter_swap(__first, __first + __half_len);
 788       } else {
 789         std::__sort3<_AlgPolicy, _Compare>(__first + __half_len, __first, __last - difference_type(1), __comp);
 790       }
 791     }
 792     // The elements to the left of the current iterator range are already
 793     // sorted.  If the current iterator range to be sorted is not the
 794     // leftmost part of the entire iterator range and the pivot is same as
 795     // the highest element in the range to the left, then we know that all
 796     // the elements in the range [first, pivot] would be equal to the pivot,
 797     // assuming the equal elements are put on the left side when
 798     // partitioned.  This also means that we do not need to sort the left
 799     // side of the partition.
 800     if (!__leftmost && !__comp(*(__first - difference_type(1)), *__first)) {
 801       __first = std::__partition_with_equals_on_left<_AlgPolicy, _RandomAccessIterator, _Comp_ref>(
 802           __first, __last, _Comp_ref(__comp));
 803       continue;
 804     }
 805     // Use bitset partition only if asked for.
 806     auto __ret =
 807         _UseBitSetPartition
 808             ? std::__bitset_partition<_AlgPolicy, _RandomAccessIterator, _Compare>(__first, __last, __comp)
 809             : std::__partition_with_equals_on_right<_AlgPolicy, _RandomAccessIterator, _Compare>(__first, __last, __comp);
 810     _RandomAccessIterator __i = __ret.first;
 811     // [__first, __i) < *__i and *__i <= [__i+1, __last)
 812     // If we were given a perfect partition, see if insertion sort is quick...
 813     if (__ret.second) {
 814       bool __fs = std::__insertion_sort_incomplete<_AlgPolicy, _Compare>(__first, __i, __comp);
 815       if (std::__insertion_sort_incomplete<_AlgPolicy, _Compare>(__i + difference_type(1), __last, __comp)) {
 816         if (__fs)
 817           return;
 818         __last = __i;
 819         continue;
 820       } else {
 821         if (__fs) {
 822           __first = ++__i;
 823           continue;
 824         }
 825       }
 826     }
 827     // Sort the left partiton recursively and the right partition with tail recursion elimination.
 828     std::__introsort<_AlgPolicy, _Compare, _RandomAccessIterator, _UseBitSetPartition>(
 829         __first, __i, __comp, __depth, __leftmost);
 830     __leftmost = false;
 831     __first    = ++__i;
 832   }
 833 }
 834
 835 template <typename _Number>
 836 inline _LIBCPP_HIDE_FROM_ABI _Number __log2i(_Number __n) {
 837   if (__n == 0)
 838     return 0;
 839   if (sizeof(__n) <= sizeof(unsigned))
 840     return sizeof(unsigned) * CHAR_BIT - 1 - __libcpp_clz(static_cast<unsigned>(__n));
 841   if (sizeof(__n) <= sizeof(unsigned long))
 842     return sizeof(unsigned long) * CHAR_BIT - 1 - __libcpp_clz(static_cast<unsigned long>(__n));
 843   if (sizeof(__n) <= sizeof(unsigned long long))
 844     return sizeof(unsigned long long) * CHAR_BIT - 1 - __libcpp_clz(static_cast<unsigned long long>(__n));
 845
 846   _Number __log2 = 0;
 847   while (__n > 1) {
 848     __log2++;
 849     __n >>= 1;
 850   }
 851   return __log2;
 852 }
 853
 854 template <class _Comp, class _RandomAccessIterator>
 855 void __sort(_RandomAccessIterator, _RandomAccessIterator, _Comp);
 856
 857 extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<char>&, char*>(char*, char*, __less<char>&);
 858 #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
 859 extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&);
 860 #endif
 861 extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&);
 862 extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&);
 863 extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<short>&, short*>(short*, short*, __less<short>&);
 864 extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&);
 865 extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<int>&, int*>(int*, int*, __less<int>&);
 866 extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&);
 867 extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<long>&, long*>(long*, long*, __less<long>&);
 868 extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&);
 869 extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<long long>&, long long*>(long long*, long long*, __less<long long>&);
 870 extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&);
 871 extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<float>&, float*>(float*, float*, __less<float>&);
 872 extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<double>&, double*>(double*, double*, __less<double>&);
 873 extern template _LIBCPP_EXPORTED_FROM_ABI void __sort<__less<long double>&, long double*>(long double*, long double*, __less<long double>&);
 874
 875 template <class _AlgPolicy, class _RandomAccessIterator, class _Comp>
 876 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void
 877 __sort_dispatch(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp& __comp) {
 878   typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
 879   difference_type __depth_limit = 2 * std::__log2i(__last - __first);
 880
 881   // Only use bitset partitioning for arithmetic types.  We should also check
 882   // that the default comparator is in use so that we are sure that there are no
 883   // branches in the comparator.
 884   std::__introsort<_AlgPolicy,
 885                    _Comp&,
 886                    _RandomAccessIterator,
 887                    __use_branchless_sort<_Comp, _RandomAccessIterator>::value>(
 888       __first, __last, __comp, __depth_limit);
 889 }
 890
 891 template <class _Type, class... _Options>
 892 using __is_any_of = _Or<is_same<_Type, _Options>...>;
 893
 894 template <class _Type>
 895 using __sort_is_specialized_in_library = __is_any_of<
 896     _Type,
 897     char,
 898 #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
 899     wchar_t,
 900 #endif
 901     signed char,
 902     unsigned char,
 903     short,
 904     unsigned short,
 905     int,
 906     unsigned int,
 907     long,
 908     unsigned long,
 909     long long,
 910     unsigned long long,
 911     float,
 912     double,
 913     long double>;
 914
 915 template <class _AlgPolicy, class _Type, __enable_if_t<__sort_is_specialized_in_library<_Type>::value, int> = 0>
 916 _LIBCPP_HIDE_FROM_ABI void __sort_dispatch(_Type* __first, _Type* __last, __less<>&) {
 917   __less<_Type> __comp;
 918   std::__sort<__less<_Type>&, _Type*>(__first, __last, __comp);
 919 }
 920
 921 template <class _AlgPolicy, class _Type, __enable_if_t<__sort_is_specialized_in_library<_Type>::value, int> = 0>
 922 _LIBCPP_HIDE_FROM_ABI void __sort_dispatch(_Type* __first, _Type* __last, less<_Type>&) {
 923   __less<_Type> __comp;
 924   std::__sort<__less<_Type>&, _Type*>(__first, __last, __comp);
 925 }
 926
 927 #if _LIBCPP_STD_VER >= 14
 928 template <class _AlgPolicy, class _Type, __enable_if_t<__sort_is_specialized_in_library<_Type>::value, int> = 0>
 929 _LIBCPP_HIDE_FROM_ABI void __sort_dispatch(_Type* __first, _Type* __last, less<>&) {
 930   __less<_Type> __comp;
 931   std::__sort<__less<_Type>&, _Type*>(__first, __last, __comp);
 932 }
 933 #endif
 934
 935 #if _LIBCPP_STD_VER >= 20
 936 template <class _AlgPolicy, class _Type, __enable_if_t<__sort_is_specialized_in_library<_Type>::value, int> = 0>
 937 _LIBCPP_HIDE_FROM_ABI void __sort_dispatch(_Type* __first, _Type* __last, ranges::less&) {
 938   __less<_Type> __comp;
 939   std::__sort<__less<_Type>&, _Type*>(__first, __last, __comp);
 940 }
 941 #endif
 942
 943 template <class _AlgPolicy, class _RandomAccessIterator, class _Comp>
 944 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
 945 void __sort_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp& __comp) {
 946   std::__debug_randomize_range<_AlgPolicy>(__first, __last);
 947
 948   if (__libcpp_is_constant_evaluated()) {
 949     std::__partial_sort<_AlgPolicy>(
 950         std::__unwrap_iter(__first), std::__unwrap_iter(__last), std::__unwrap_iter(__last), __comp);
 951   } else {
 952     std::__sort_dispatch<_AlgPolicy>(std::__unwrap_iter(__first), std::__unwrap_iter(__last), __comp);
 953   }
 954   std::__check_strict_weak_ordering_sorted(std::__unwrap_iter(__first), std::__unwrap_iter(__last), __comp);
 955 }
 956
 957 template <class _RandomAccessIterator, class _Comp>
 958 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
 959 void sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp) {
 960   std::__sort_impl<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp);
 961 }
 962
 963 template <class _RandomAccessIterator>
 964 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
 965 void sort(_RandomAccessIterator __first, _RandomAccessIterator __last) {
 966   std::sort(__first, __last, __less<>());
 967 }
 968
 969 _LIBCPP_END_NAMESPACE_STD
 970
 971 #endif // _LIBCPP___ALGORITHM_SORT_H