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