[libc++] Add an early return for __partial_sort of an empty range.

[• Quuxplusone]

Summary

If __first == __middle, then partial_sort is a no-op; don't bother to iterate all the way from __middle to __end.

Fixes https://github.com/llvm/llvm-project/issues/49431

[philnik]

libcxx/include/__algorithm/partial_sort.h

33–34

Nit, but this patch seems small enough to change that.

[jloser]

Any appetite for adding a test that counts the numbers of comparisons to bind this behavior? Otherwise, LGTM!

[ldionne]

LGTM, but I agree it would be good to add a test to avoid regressing that if we change our partial_sort implementation (which we might very well do at some point, since there is some work happening on std::sort).

[ldionne]

BTW, that was not binding -- as discussed offline, I think it is reasonable to try to tackle complexity tests separately from this patch, and more generally for all the algorithms.

libcxx/include/__algorithm/partial_sort.h

 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template <class _Compare, class _RandomAccessIterator>
 _LIBCPP_CONSTEXPR_AFTER_CXX17 void
 __partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
              _Compare __comp)
 {
+    if (__first == __middle)
+        return;
     _VSTD::__make_heap<_Compare>(__first, __middle, __comp);
     typename iterator_traits<_RandomAccessIterator>::difference_type __len = __middle - __first;
     for (_RandomAccessIterator __i = __middle; __i != __last; ++__i)
     {
         if (__comp(*__i, *__first))
         {
             swap(*__i, *__first);
             _VSTD::__sift_down<_Compare>(__first, __comp, __len, __first);