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