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 <__config>
13 #include <__algorithm/comp.h>
14 #include <__algorithm/comp_ref_type.h>
15 #include <__algorithm/min_element.h>
16 #include <__algorithm/partial_sort.h>
17 #include <__algorithm/unwrap_iter.h>
18 #include <__utility/swap.h>
19 #include <memory>
20 #include <type_traits> // swap
21 
22 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
23 #pragma GCC system_header
24 #endif
25 
26 _LIBCPP_PUSH_MACROS
27 #include <__undef_macros>
28 
29 _LIBCPP_BEGIN_NAMESPACE_STD
30 
31 // stable, 2-3 compares, 0-2 swaps
32 
33 template <class _Compare, class _ForwardIterator>
34 _LIBCPP_CONSTEXPR_AFTER_CXX11 unsigned
__sort3(_ForwardIterator __x,_ForwardIterator __y,_ForwardIterator __z,_Compare __c)35 __sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, _Compare __c)
36 {
37     unsigned __r = 0;
38     if (!__c(*__y, *__x))          // if x <= y
39     {
40         if (!__c(*__z, *__y))      // if y <= z
41             return __r;            // x <= y && y <= z
42                                    // x <= y && y > z
43         swap(*__y, *__z);          // x <= z && y < z
44         __r = 1;
45         if (__c(*__y, *__x))       // if x > y
46         {
47             swap(*__x, *__y);      // x < y && y <= z
48             __r = 2;
49         }
50         return __r;                // x <= y && y < z
51     }
52     if (__c(*__z, *__y))           // x > y, if y > z
53     {
54         swap(*__x, *__z);          // x < y && y < z
55         __r = 1;
56         return __r;
57     }
58     swap(*__x, *__y);              // x > y && y <= z
59     __r = 1;                       // x < y && x <= z
60     if (__c(*__z, *__y))           // if y > z
61     {
62         swap(*__y, *__z);          // x <= y && y < z
63         __r = 2;
64     }
65     return __r;
66 }                                  // x <= y && y <= z
67 
68 // stable, 3-6 compares, 0-5 swaps
69 
70 template <class _Compare, class _ForwardIterator>
71 unsigned
__sort4(_ForwardIterator __x1,_ForwardIterator __x2,_ForwardIterator __x3,_ForwardIterator __x4,_Compare __c)72 __sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
73             _ForwardIterator __x4, _Compare __c)
74 {
75     unsigned __r = _VSTD::__sort3<_Compare>(__x1, __x2, __x3, __c);
76     if (__c(*__x4, *__x3))
77     {
78         swap(*__x3, *__x4);
79         ++__r;
80         if (__c(*__x3, *__x2))
81         {
82             swap(*__x2, *__x3);
83             ++__r;
84             if (__c(*__x2, *__x1))
85             {
86                 swap(*__x1, *__x2);
87                 ++__r;
88             }
89         }
90     }
91     return __r;
92 }
93 
94 // stable, 4-10 compares, 0-9 swaps
95 
96 template <class _Compare, class _ForwardIterator>
97 _LIBCPP_HIDDEN
98 unsigned
__sort5(_ForwardIterator __x1,_ForwardIterator __x2,_ForwardIterator __x3,_ForwardIterator __x4,_ForwardIterator __x5,_Compare __c)99 __sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
100             _ForwardIterator __x4, _ForwardIterator __x5, _Compare __c)
101 {
102     unsigned __r = _VSTD::__sort4<_Compare>(__x1, __x2, __x3, __x4, __c);
103     if (__c(*__x5, *__x4))
104     {
105         swap(*__x4, *__x5);
106         ++__r;
107         if (__c(*__x4, *__x3))
108         {
109             swap(*__x3, *__x4);
110             ++__r;
111             if (__c(*__x3, *__x2))
112             {
113                 swap(*__x2, *__x3);
114                 ++__r;
115                 if (__c(*__x2, *__x1))
116                 {
117                     swap(*__x1, *__x2);
118                     ++__r;
119                 }
120             }
121         }
122     }
123     return __r;
124 }
125 
126 // Assumes size > 0
127 template <class _Compare, class _BidirectionalIterator>
128 _LIBCPP_CONSTEXPR_AFTER_CXX11 void
__selection_sort(_BidirectionalIterator __first,_BidirectionalIterator __last,_Compare __comp)129 __selection_sort(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
130 {
131     _BidirectionalIterator __lm1 = __last;
132     for (--__lm1; __first != __lm1; ++__first)
133     {
134         _BidirectionalIterator __i = _VSTD::min_element<_BidirectionalIterator,
135                                                         typename add_lvalue_reference<_Compare>::type>
136                                                        (__first, __last, __comp);
137         if (__i != __first)
138             swap(*__first, *__i);
139     }
140 }
141 
142 template <class _Compare, class _BidirectionalIterator>
143 void
__insertion_sort(_BidirectionalIterator __first,_BidirectionalIterator __last,_Compare __comp)144 __insertion_sort(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
145 {
146     typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
147     if (__first != __last)
148     {
149         _BidirectionalIterator __i = __first;
150         for (++__i; __i != __last; ++__i)
151         {
152             _BidirectionalIterator __j = __i;
153             value_type __t(_VSTD::move(*__j));
154             for (_BidirectionalIterator __k = __i; __k != __first && __comp(__t,  *--__k); --__j)
155                 *__j = _VSTD::move(*__k);
156             *__j = _VSTD::move(__t);
157         }
158     }
159 }
160 
161 template <class _Compare, class _RandomAccessIterator>
162 void
__insertion_sort_3(_RandomAccessIterator __first,_RandomAccessIterator __last,_Compare __comp)163 __insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
164 {
165     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
166     _RandomAccessIterator __j = __first+2;
167     _VSTD::__sort3<_Compare>(__first, __first+1, __j, __comp);
168     for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i)
169     {
170         if (__comp(*__i, *__j))
171         {
172             value_type __t(_VSTD::move(*__i));
173             _RandomAccessIterator __k = __j;
174             __j = __i;
175             do
176             {
177                 *__j = _VSTD::move(*__k);
178                 __j = __k;
179             } while (__j != __first && __comp(__t, *--__k));
180             *__j = _VSTD::move(__t);
181         }
182         __j = __i;
183     }
184 }
185 
186 template <class _Compare, class _RandomAccessIterator>
187 bool
__insertion_sort_incomplete(_RandomAccessIterator __first,_RandomAccessIterator __last,_Compare __comp)188 __insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
189 {
190     switch (__last - __first)
191     {
192     case 0:
193     case 1:
194         return true;
195     case 2:
196         if (__comp(*--__last, *__first))
197             swap(*__first, *__last);
198         return true;
199     case 3:
200         _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
201         return true;
202     case 4:
203         _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
204         return true;
205     case 5:
206         _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
207         return true;
208     }
209     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
210     _RandomAccessIterator __j = __first+2;
211     _VSTD::__sort3<_Compare>(__first, __first+1, __j, __comp);
212     const unsigned __limit = 8;
213     unsigned __count = 0;
214     for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i)
215     {
216         if (__comp(*__i, *__j))
217         {
218             value_type __t(_VSTD::move(*__i));
219             _RandomAccessIterator __k = __j;
220             __j = __i;
221             do
222             {
223                 *__j = _VSTD::move(*__k);
224                 __j = __k;
225             } while (__j != __first && __comp(__t, *--__k));
226             *__j = _VSTD::move(__t);
227             if (++__count == __limit)
228                 return ++__i == __last;
229         }
230         __j = __i;
231     }
232     return true;
233 }
234 
235 template <class _Compare, class _BidirectionalIterator>
236 void
__insertion_sort_move(_BidirectionalIterator __first1,_BidirectionalIterator __last1,typename iterator_traits<_BidirectionalIterator>::value_type * __first2,_Compare __comp)237 __insertion_sort_move(_BidirectionalIterator __first1, _BidirectionalIterator __last1,
238                       typename iterator_traits<_BidirectionalIterator>::value_type* __first2, _Compare __comp)
239 {
240     typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
241     if (__first1 != __last1)
242     {
243         __destruct_n __d(0);
244         unique_ptr<value_type, __destruct_n&> __h(__first2, __d);
245         value_type* __last2 = __first2;
246         ::new ((void*)__last2) value_type(_VSTD::move(*__first1));
247         __d.template __incr<value_type>();
248         for (++__last2; ++__first1 != __last1; ++__last2)
249         {
250             value_type* __j2 = __last2;
251             value_type* __i2 = __j2;
252             if (__comp(*__first1, *--__i2))
253             {
254                 ::new ((void*)__j2) value_type(_VSTD::move(*__i2));
255                 __d.template __incr<value_type>();
256                 for (--__j2; __i2 != __first2 && __comp(*__first1,  *--__i2); --__j2)
257                     *__j2 = _VSTD::move(*__i2);
258                 *__j2 = _VSTD::move(*__first1);
259             }
260             else
261             {
262                 ::new ((void*)__j2) value_type(_VSTD::move(*__first1));
263                 __d.template __incr<value_type>();
264             }
265         }
266         __h.release();
267     }
268 }
269 
270 template <class _Compare, class _RandomAccessIterator>
271 void
__sort(_RandomAccessIterator __first,_RandomAccessIterator __last,_Compare __comp)272 __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
273 {
274     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
275     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
276     const difference_type __limit = is_trivially_copy_constructible<value_type>::value &&
277                                     is_trivially_copy_assignable<value_type>::value ? 30 : 6;
278     while (true)
279     {
280     __restart:
281         difference_type __len = __last - __first;
282         switch (__len)
283         {
284         case 0:
285         case 1:
286             return;
287         case 2:
288             if (__comp(*--__last, *__first))
289                 swap(*__first, *__last);
290             return;
291         case 3:
292             _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
293             return;
294         case 4:
295             _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
296             return;
297         case 5:
298             _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
299             return;
300         }
301         if (__len <= __limit)
302         {
303             _VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp);
304             return;
305         }
306         // __len > 5
307         _RandomAccessIterator __m = __first;
308         _RandomAccessIterator __lm1 = __last;
309         --__lm1;
310         unsigned __n_swaps;
311         {
312         difference_type __delta;
313         if (__len >= 1000)
314         {
315             __delta = __len/2;
316             __m += __delta;
317             __delta /= 2;
318             __n_swaps = _VSTD::__sort5<_Compare>(__first, __first + __delta, __m, __m+__delta, __lm1, __comp);
319         }
320         else
321         {
322             __delta = __len/2;
323             __m += __delta;
324             __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, __lm1, __comp);
325         }
326         }
327         // *__m is median
328         // partition [__first, __m) < *__m and *__m <= [__m, __last)
329         // (this inhibits tossing elements equivalent to __m around unnecessarily)
330         _RandomAccessIterator __i = __first;
331         _RandomAccessIterator __j = __lm1;
332         // j points beyond range to be tested, *__m is known to be <= *__lm1
333         // The search going up is known to be guarded but the search coming down isn't.
334         // Prime the downward search with a guard.
335         if (!__comp(*__i, *__m))  // if *__first == *__m
336         {
337             // *__first == *__m, *__first doesn't go in first part
338             // manually guard downward moving __j against __i
339             while (true)
340             {
341                 if (__i == --__j)
342                 {
343                     // *__first == *__m, *__m <= all other elements
344                     // Parition instead into [__first, __i) == *__first and *__first < [__i, __last)
345                     ++__i;  // __first + 1
346                     __j = __last;
347                     if (!__comp(*__first, *--__j))  // we need a guard if *__first == *(__last-1)
348                     {
349                         while (true)
350                         {
351                             if (__i == __j)
352                                 return;  // [__first, __last) all equivalent elements
353                             if (__comp(*__first, *__i))
354                             {
355                                 swap(*__i, *__j);
356                                 ++__n_swaps;
357                                 ++__i;
358                                 break;
359                             }
360                             ++__i;
361                         }
362                     }
363                     // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
364                     if (__i == __j)
365                         return;
366                     while (true)
367                     {
368                         while (!__comp(*__first, *__i))
369                             ++__i;
370                         while (__comp(*__first, *--__j))
371                             ;
372                         if (__i >= __j)
373                             break;
374                         swap(*__i, *__j);
375                         ++__n_swaps;
376                         ++__i;
377                     }
378                     // [__first, __i) == *__first and *__first < [__i, __last)
379                     // The first part is sorted, sort the second part
380                     // _VSTD::__sort<_Compare>(__i, __last, __comp);
381                     __first = __i;
382                     goto __restart;
383                 }
384                 if (__comp(*__j, *__m))
385                 {
386                     swap(*__i, *__j);
387                     ++__n_swaps;
388                     break;  // found guard for downward moving __j, now use unguarded partition
389                 }
390             }
391         }
392         // It is known that *__i < *__m
393         ++__i;
394         // j points beyond range to be tested, *__m is known to be <= *__lm1
395         // if not yet partitioned...
396         if (__i < __j)
397         {
398             // known that *(__i - 1) < *__m
399             // known that __i <= __m
400             while (true)
401             {
402                 // __m still guards upward moving __i
403                 while (__comp(*__i, *__m))
404                     ++__i;
405                 // It is now known that a guard exists for downward moving __j
406                 while (!__comp(*--__j, *__m))
407                     ;
408                 if (__i > __j)
409                     break;
410                 swap(*__i, *__j);
411                 ++__n_swaps;
412                 // It is known that __m != __j
413                 // If __m just moved, follow it
414                 if (__m == __i)
415                     __m = __j;
416                 ++__i;
417             }
418         }
419         // [__first, __i) < *__m and *__m <= [__i, __last)
420         if (__i != __m && __comp(*__m, *__i))
421         {
422             swap(*__i, *__m);
423             ++__n_swaps;
424         }
425         // [__first, __i) < *__i and *__i <= [__i+1, __last)
426         // If we were given a perfect partition, see if insertion sort is quick...
427         if (__n_swaps == 0)
428         {
429             bool __fs = _VSTD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp);
430             if (_VSTD::__insertion_sort_incomplete<_Compare>(__i+1, __last, __comp))
431             {
432                 if (__fs)
433                     return;
434                 __last = __i;
435                 continue;
436             }
437             else
438             {
439                 if (__fs)
440                 {
441                     __first = ++__i;
442                     continue;
443                 }
444             }
445         }
446         // sort smaller range with recursive call and larger with tail recursion elimination
447         if (__i - __first < __last - __i)
448         {
449             _VSTD::__sort<_Compare>(__first, __i, __comp);
450             // _VSTD::__sort<_Compare>(__i+1, __last, __comp);
451             __first = ++__i;
452         }
453         else
454         {
455             _VSTD::__sort<_Compare>(__i+1, __last, __comp);
456             // _VSTD::__sort<_Compare>(__first, __i, __comp);
457             __last = __i;
458         }
459     }
460 }
461 
462 template <class _Compare, class _Tp>
463 inline _LIBCPP_INLINE_VISIBILITY
464 void
__sort(_Tp ** __first,_Tp ** __last,__less<_Tp * > &)465 __sort(_Tp** __first, _Tp** __last, __less<_Tp*>&)
466 {
467     __less<uintptr_t> __comp;
468     _VSTD::__sort<__less<uintptr_t>&, uintptr_t*>((uintptr_t*)__first, (uintptr_t*)__last, __comp);
469 }
470 
_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<char> &,char * > (char *,char *,__less<char> &))471 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<char>&, char*>(char*, char*, __less<char>&))
472 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&))
473 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&))
474 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&))
475 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<short>&, short*>(short*, short*, __less<short>&))
476 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&))
477 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<int>&, int*>(int*, int*, __less<int>&))
478 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&))
479 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long>&, long*>(long*, long*, __less<long>&))
480 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&))
481 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long long>&, long long*>(long long*, long long*, __less<long long>&))
482 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&))
483 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<float>&, float*>(float*, float*, __less<float>&))
484 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<double>&, double*>(double*, double*, __less<double>&))
485 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long double>&, long double*>(long double*, long double*, __less<long double>&))
486 
487 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<char>&, char*>(char*, char*, __less<char>&))
488 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&))
489 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&))
490 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&))
491 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<short>&, short*>(short*, short*, __less<short>&))
492 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&))
493 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<int>&, int*>(int*, int*, __less<int>&))
494 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&))
495 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long>&, long*>(long*, long*, __less<long>&))
496 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&))
497 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long long>&, long long*>(long long*, long long*, __less<long long>&))
498 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&))
499 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<float>&, float*>(float*, float*, __less<float>&))
500 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<double>&, double*>(double*, double*, __less<double>&))
501 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long double>&, long double*>(long double*, long double*, __less<long double>&))
502 
503 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS unsigned __sort5<__less<long double>&, long double*>(long double*, long double*, long double*, long double*, long double*, __less<long double>&))
504 
505 template <class _RandomAccessIterator, class _Compare>
506 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
507 void
508 sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
509 {
510     typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
511     if (__libcpp_is_constant_evaluated()) {
512         _VSTD::__partial_sort<_Comp_ref>(__first, __last, __last, _Comp_ref(__comp));
513     } else {
514         _VSTD::__sort<_Comp_ref>(_VSTD::__unwrap_iter(__first), _VSTD::__unwrap_iter(__last), _Comp_ref(__comp));
515     }
516 }
517 
518 template <class _RandomAccessIterator>
519 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
520 void
sort(_RandomAccessIterator __first,_RandomAccessIterator __last)521 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
522 {
523     _VSTD::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
524 }
525 
526 _LIBCPP_END_NAMESPACE_STD
527 
528 _LIBCPP_POP_MACROS
529 
530 #endif // _LIBCPP___ALGORITHM_SORT_H
531