[libc++][ranges] implement `std::ranges::inplace_merge`

[huixie90]

implement tests

[huixie90]

rebase

[huixie90]

fix CI

[var-const]

Thanks a lot! A few nitpicks, and let's discuss algorithm_family.h offline (I'll post a summary here afterwards).

libcxx/docs/Status/RangesAlgorithms.csv

80 ↗

(On Diff #448109)

The patch number needs to be updated.

libcxx/include/__algorithm/inplace_merge.h

50

Nit: it's best not to do these refactoring changes in this patch (for the lines that you don't otherwise modify). It increases the delta that needs to be reviewed, but more importantly, it makes it harder to navigate git blame. Ideally, such changes should go to dedicated refactoring patches which can then be added to .git-blame-ignore-revs.

This doesn't apply to the lines that you're modifying anyway -- since those would show up in git blame regardless, might as well refactor them.

libcxx/test/std/algorithms/alg.sorting/alg.merge/ranges_inplace_merge.pass.cpp

62

Nit: "yet" makes it a little ambiguous whether it's not constexpr in the standard or just in our implementation. I'd rephrase to inplace_merge is not constexpr in the latest finished Standard.

94

Optional: consider asserting that (input.begin(), input.begin() + midIdx) and (input.begin() + midIdx, input.end()) are is_sorted.

125

Missing [first, mid).

146

Nit: s/duplictes/duplicates/.

167

Consider also checking mid == first + 1 and mid == last - 1 (to check for off-by-one errors).

275

Please copy the specification from the standard into this comment.

294

Ultranits: s/specify/specifies/ and s/does not/don't/.

294

I noticed the same with shuffle. It could be a simple oversight in the spec.

[huixie90]

address review feedback

[huixie90]

add newline

[var-const]

libcxx/include/__algorithm/algorithm_family.h

26

Nit: since we're using _AlgPolicy, this should be _AlgFamily (no o).

[huixie90]

address comments

libcxx/include/CMakeLists.txt

 set(files
   __algorithm/adjacent_find.h
+  __algorithm/algorithm_family.h
   __algorithm/all_of.h
   __algorithm/any_of.h
   __algorithm/binary_search.h
   __algorithm/clamp.h
   __algorithm/comp.h
   __algorithm/comp_ref_type.h
   __algorithm/copy.h
   __algorithm/copy_backward.h

libcxx/include/__algorithm/algorithm_family.h

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___ALGORITHM_ALGORITHM_FAMILY_H
+#define _LIBCPP___ALGORITHM_ALGORITHM_FAMILY_H
+
+#include <__algorithm/iterator_operations.h>
+#include <__algorithm/move.h>
+#include <__algorithm/ranges_move.h>
+#include <__config>
+#include <__utility/move.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template <class _AlgPolicy>
+struct _AlgoFamily;
+
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+template <>
+struct _AlgoFamily<_RangeAlgPolicy> {
+  static constexpr auto __move = ranges::move;
+};
+
+#endif
+
+template <>
+struct _AlgoFamily<_ClassicAlgPolicy> {
+
+  // move
+  template <class _InputIterator, class _OutputIterator>
+  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 static _OutputIterator
+  __move(_InputIterator __first, _InputIterator __last, _OutputIterator __result) {
+    return std::move(
+        std::move(__first),
+        std::move(__last),
+        std::move(__result));
+  }
+};
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP___ALGORITHM_ALGORITHM_FAMILY_H

libcxx/include/__algorithm/inplace_merge.h

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_INPLACE_MERGE_H
 #define _LIBCPP___ALGORITHM_INPLACE_MERGE_H
 
+#include <__algorithm/algorithm_family.h>
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
 #include <__algorithm/iterator_operations.h>
 #include <__algorithm/lower_bound.h>
 #include <__algorithm/min.h>
 #include <__algorithm/move.h>
 #include <__algorithm/rotate.h>
 #include <__algorithm/upper_bound.h>

 #include <__undef_macros>
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template <class _Predicate>
 class __invert // invert the sense of a comparison
 {
 private:
-    _Predicate __p_;
+
 public:
-    _LIBCPP_INLINE_VISIBILITY __invert() {}
+  _LIBCPP_HIDE_FROM_ABI __invert() {}
 
-    _LIBCPP_INLINE_VISIBILITY
-    explicit __invert(_Predicate __p) : __p_(__p) {}
+  _LIBCPP_HIDE_FROM_ABI explicit __invert(_Predicate __p) : __p_(__p) {}
 
-    template <class _T1>
-    _LIBCPP_INLINE_VISIBILITY
-    bool operator()(const _T1& __x) {return !__p_(__x);}
+  _LIBCPP_HIDE_FROM_ABI bool operator()(const _T1& __x) {
+    return !__p_(__x);
+  }
 
-    template <class _T1, class _T2>
-    _LIBCPP_INLINE_VISIBILITY
-    bool operator()(const _T1& __x, const _T2& __y) {return __p_(__y, __x);}
+  _LIBCPP_HIDE_FROM_ABI bool operator()(const _T1& __x, const _T2& __y) {
+    return __p_(__y, __x);
+  }
 };
 
-template <class _AlgPolicy, class _Compare, class _InputIterator1, class _InputIterator2,
-          class _OutputIterator>
-void __half_inplace_merge(_InputIterator1 __first1, _InputIterator1 __last1,
-                          _InputIterator2 __first2, _InputIterator2 __last2,
-                          _OutputIterator __result, _Compare __comp)
-{
-    for (; __first1 != __last1; ++__result)
-    {
-        if (__first2 == __last2)
-        {
-            // TODO(alg-policy): pass `_AlgPolicy` once it's supported by `move`.
-            _VSTD::move(__first1, __last1, __result);
-            return;
-        }
+template <
+    class _AlgPolicy,
+    class _Compare,
+    class _InputIterator1,
+    class _Sent1,
+    class _InputIterator2,
+    class _Sent2,
+_LIBCPP_HIDE_FROM_ABI void __half_inplace_merge(
+    _InputIterator1 __first1,
+    _Sent1 __last1,
+    _InputIterator2 __first2,
+    _Sent2 __last2,
+    _OutputIterator __result,
+    _Compare&& __comp) {
+  for (; __first1 != __last1; ++__result) {
+    if (__first2 == __last2) {
+      _AlgoFamily<_AlgPolicy>::__move(__first1, __last1, __result);
 
-        if (__comp(*__first2, *__first1))
-        {
-            *__result = _IterOps<_AlgPolicy>::__iter_move(__first2);
-            ++__first2;
-        }
-        else
-        {
-            *__result = _IterOps<_AlgPolicy>::__iter_move(__first1);
-            ++__first1;
-        }
-    }
-    // __first2 through __last2 are already in the right spot.
+    if (__comp(*__first2, *__first1)) {
+    } else {
 }
 
 template <class _AlgPolicy, class _Compare, class _BidirectionalIterator>
-void
-__buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
-                _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
-                                 typename iterator_traits<_BidirectionalIterator>::difference_type __len2,
-                typename iterator_traits<_BidirectionalIterator>::value_type* __buff)
-{
-    typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
-    __destruct_n __d(0);
-    unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);
-    if (__len1 <= __len2)
-    {
-        value_type* __p = __buff;
-        for (_BidirectionalIterator __i = __first; __i != __middle; __d.template __incr<value_type>(), (void) ++__i, (void) ++__p)
-            ::new ((void*)__p) value_type(_IterOps<_AlgPolicy>::__iter_move(__i));
-        std::__half_inplace_merge<_AlgPolicy, _Compare>(__buff, __p, __middle, __last, __first, __comp);
-    }
-    else
-    {
-        value_type* __p = __buff;
-        for (_BidirectionalIterator __i = __middle; __i != __last; __d.template __incr<value_type>(), (void) ++__i, (void) ++__p)
-            ::new ((void*)__p) value_type(_IterOps<_AlgPolicy>::__iter_move(__i));
-        typedef __unconstrained_reverse_iterator<_BidirectionalIterator> _RBi;
-        typedef __unconstrained_reverse_iterator<value_type*> _Rv;
-        typedef __invert<_Compare> _Inverted;
-        std::__half_inplace_merge<_AlgPolicy, _Inverted>(_Rv(__p), _Rv(__buff),
-                                    _RBi(__middle), _RBi(__first),
-                                    _RBi(__last), _Inverted(__comp));
-    }
+_LIBCPP_HIDE_FROM_ABI void __buffered_inplace_merge(
+    _BidirectionalIterator __first,
+    _BidirectionalIterator __middle,
+    _BidirectionalIterator __last,
+    _Compare&& __comp,
+    typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
+    typename iterator_traits<_BidirectionalIterator>::value_type* __buff) {
+  if (__len1 <= __len2) {
+    for (_BidirectionalIterator __i = __first; __i != __middle;
+         __d.template __incr<value_type>(), (void)++__i, (void)++__p)
+    std::__half_inplace_merge<_AlgPolicy>(__buff, __p, __middle, __last, __first, __comp);
+  } else {
+    for (_BidirectionalIterator __i = __middle; __i != __last;
+         __d.template __incr<value_type>(), (void)++__i, (void)++__p)
+    std::__half_inplace_merge<_AlgPolicy>(
+        _Rv(__p), _Rv(__buff), _RBi(__middle), _RBi(__first), _RBi(__last), _Inverted(__comp));
 }
 
 template <class _AlgPolicy, class _Compare, class _BidirectionalIterator>
-void
-__inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
-                _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
-                                 typename iterator_traits<_BidirectionalIterator>::difference_type __len2,
-                typename iterator_traits<_BidirectionalIterator>::value_type* __buff, ptrdiff_t __buff_size)
-{
-    using _Ops = _IterOps<_AlgPolicy>;
+ void __inplace_merge(
+    _BidirectionalIterator __first,
+    _BidirectionalIterator __middle,
+    _BidirectionalIterator __last,
+    _Compare&& __comp,
+    typename iterator_traits<_BidirectionalIterator>::difference_type __len1,
+    typename iterator_traits<_BidirectionalIterator>::value_type* __buff,
+    ptrdiff_t __buff_size) {
 
-    typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
-    while (true)
-    {
-        // if __middle == __last, we're done
-        if (__len2 == 0)
-            return;
-        if (__len1 <= __buff_size || __len2 <= __buff_size)
-            return std::__buffered_inplace_merge<_AlgPolicy, _Compare>
-                   (__first, __middle, __last, __comp, __len1, __len2, __buff);
-        // shrink [__first, __middle) as much as possible (with no moves), returning if it shrinks to 0
-        for (; true; ++__first, (void) --__len1)
-        {
-            if (__len1 == 0)
-                return;
-            if (__comp(*__middle, *__first))
-                break;
-        }
-        // __first < __middle < __last
-        // *__first > *__middle
-        // partition [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) such that
-        //     all elements in:
-        //         [__first, __m1)  <= [__middle, __m2)
-        //         [__middle, __m2) <  [__m1, __middle)
-        //         [__m1, __middle) <= [__m2, __last)
-        //     and __m1 or __m2 is in the middle of its range
-        _BidirectionalIterator __m1;  // "median" of [__first, __middle)
-        _BidirectionalIterator __m2;  // "median" of [__middle, __last)
-        difference_type __len11;      // distance(__first, __m1)
-        difference_type __len21;      // distance(__middle, __m2)
-        // binary search smaller range
-        if (__len1 < __len2)
-        {   // __len >= 1, __len2 >= 2
-            __len21 = __len2 / 2;
-            __m2 = __middle;
-            _Ops::advance(__m2, __len21);
-            // TODO: replace _ClassicAlgPolicy and __identity with _AlgPolicy and projection
-            __m1 = std::__upper_bound<_ClassicAlgPolicy>(__first, __middle, *__m2, __comp, std::__identity());
-            __len11 = _Ops::distance(__first, __m1);
-        }
-        else
-        {
-            if (__len1 == 1)
-            {   // __len1 >= __len2 && __len2 > 0, therefore __len2 == 1
-                // It is known *__first > *__middle
-              _Ops::iter_swap(__first, __middle);
-                return;
-            }
-            // __len1 >= 2, __len2 >= 1
-            __len11 = __len1 / 2;
-            __m1 = __first;
-            _Ops::advance(__m1, __len11);
-            __m2 = std::lower_bound(__middle, __last, *__m1, __comp);
-            __len21 = _Ops::distance(__middle, __m2);
-        }
-        difference_type __len12 = __len1 - __len11;  // distance(__m1, __middle)
-        difference_type __len22 = __len2 - __len21;  // distance(__m2, __last)
-        // [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last)
-        // swap middle two partitions
-        // TODO(alg-policy): pass `_AlgPolicy` once it's supported by `rotate`.
-        __middle = _VSTD::rotate(__m1, __middle, __m2);
-        // __len12 and __len21 now have swapped meanings
-        // merge smaller range with recursive call and larger with tail recursion elimination
-        if (__len11 + __len21 < __len12 + __len22)
-        {
-            std::__inplace_merge<_AlgPolicy, _Compare>(
-                __first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
-//          _VSTD::__inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
-            __first = __middle;
-            __middle = __m2;
-            __len1 = __len12;
-            __len2 = __len22;
-        }
-        else
-        {
-            std::__inplace_merge<_AlgPolicy, _Compare>(
-                __middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
-//          _VSTD::__inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
-            __last = __middle;
-            __middle = __m1;
-            __len1 = __len11;
-            __len2 = __len21;
-        }
-    }
+  while (true) {
+      return std::__buffered_inplace_merge<_AlgPolicy>(__first, __middle, __last, __comp, __len1, __len2, __buff);
+    for (; true; ++__first, (void)--__len1) {
+    _BidirectionalIterator __m1; // "median" of [__first, __middle)
+    _BidirectionalIterator __m2; // "median" of [__middle, __last)
+    difference_type __len11;     // distance(__first, __m1)
+    difference_type __len21;     // distance(__middle, __m2)
+    if (__len1 < __len2) { // __len >= 1, __len2 >= 2
+      __m2    = __middle;
+      __m1    = std::__upper_bound<_ClassicAlgPolicy>(__first, __middle, *__m2, __comp, std::__identity());
+    } else {
+      if (__len1 == 1) { // __len1 >= __len2 && __len2 > 0, therefore __len2 == 1
+      __m1    = __first;
+      __m2    = std::lower_bound(__middle, __last, *__m1, __comp);
+    difference_type __len12 = __len1 - __len11; // distance(__m1, __middle)
+    difference_type __len22 = __len2 - __len21; // distance(__m2, __last)
+    if (__len11 + __len21 < __len12 + __len22) {
+      std::__inplace_merge<_AlgPolicy>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
+      __first  = __middle;
+      __len1   = __len12;
+      __len2   = __len22;
+    } else {
+      std::__inplace_merge<_AlgPolicy>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);
+      __last   = __middle;
+      __len1   = __len11;
+      __len2   = __len21;
 }
 
-template <class _BidirectionalIterator, class _Compare>
-inline _LIBCPP_INLINE_VISIBILITY
-void
-inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last,
-              _Compare __comp)
-{
-    typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type;
-    typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type;
-    difference_type __len1 = _VSTD::distance(__first, __middle);
-    difference_type __len2 = _VSTD::distance(__middle, __last);
-    difference_type __buf_size = _VSTD::min(__len1, __len2);
+template <class _AlgPolicy, class _BidirectionalIterator, class _Compare>
+_LIBCPP_HIDE_FROM_ABI void __inplace_merge(
+    _BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Compare&& __comp) {
+  difference_type __len1     = _IterOps<_AlgPolicy>::distance(__first, __middle);
+  difference_type __len2     = _IterOps<_AlgPolicy>::distance(__middle, __last);
   // TODO: Remove the use of std::get_temporary_buffer
   _LIBCPP_SUPPRESS_DEPRECATED_PUSH
-    pair<value_type*, ptrdiff_t> __buf = _VSTD::get_temporary_buffer<value_type>(__buf_size);
   _LIBCPP_SUPPRESS_DEPRECATED_POP
-    unique_ptr<value_type, __return_temporary_buffer> __h(__buf.first);
-    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
-    return _VSTD::__inplace_merge<_ClassicAlgPolicy, _Comp_ref>(__first, __middle, __last, __comp, __len1, __len2,
-                                            __buf.first, __buf.second);
+  std::__inplace_merge<_AlgPolicy>(
+      std::move(__first), std::move(__middle), std::move(__last), __comp, __len1, __len2, __buf.first, __buf.second);
+}
+
+template <class _BidirectionalIterator, class _Compare>
+inline _LIBCPP_HIDE_FROM_ABI void inplace_merge(
+    _BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Compare __comp) {
+  std::__inplace_merge<_ClassicAlgPolicy>(
+      std::move(__first), std::move(__middle), std::move(__last), static_cast<_Comp_ref>(__comp));
 }
 
 template <class _BidirectionalIterator>
-inline _LIBCPP_INLINE_VISIBILITY
-void
-inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last)
-{
-    _VSTD::inplace_merge(__first, __middle, __last,
-                        __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
+inline _LIBCPP_HIDE_FROM_ABI void
+inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last) {
+  std::inplace_merge(__first, __middle, __last, __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #endif // _LIBCPP___ALGORITHM_INPLACE_MERGE_H

libcxx/include/__algorithm/ranges_inplace_merge.h

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_RANGES_INPLACE_MERGE_H
 #define _LIBCPP___ALGORITHM_RANGES_INPLACE_MERGE_H
 
 #include <__algorithm/inplace_merge.h>
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/make_projected.h>
 #include <__config>
 #include <__functional/identity.h>
 #include <__functional/invoke.h>
 #include <__functional/ranges_operations.h>
 #include <__iterator/concepts.h>
 #include <__iterator/iterator_traits.h>
+#include <__iterator/next.h>
 #include <__iterator/projected.h>
 #include <__iterator/sortable.h>
 #include <__ranges/access.h>
 #include <__ranges/concepts.h>
 #include <__ranges/dangling.h>
 #include <__utility/forward.h>
 #include <__utility/move.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 #if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 namespace ranges {
 namespace __inplace_merge {
 
   struct __fn {
+    template <class _Iter, class _Sent, class _Comp, class _Proj>
+    _LIBCPP_HIDE_FROM_ABI static constexpr auto
+    __inplace_merge_impl(_Iter __first, _Iter __middle, _Sent __last, _Comp&& __comp, _Proj&& __proj) {
+      auto __last_iter = ranges::next(__middle, __last);
+      std::__inplace_merge<_RangeAlgPolicy>(
+          std::move(__first), std::move(__middle), __last_iter, ranges::__make_projected_comp(__comp, __proj));
+      return __last_iter;
+    }
 
-  template <bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent, class _Comp = ranges::less, class _Proj = identity>
+    template <
+        bidirectional_iterator _Iter,
+        sentinel_for<_Iter> _Sent,
+        class _Comp = ranges::less,
+        class _Proj = identity>
       requires sortable<_Iter, _Comp, _Proj>
-  _LIBCPP_HIDE_FROM_ABI
-  _Iter operator()(_Iter __first, _Iter __middle, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const {
-    // TODO: implement
-    (void)__first; (void)__middle; (void)__last; (void)__comp; (void)__proj;
-    return {};
+    _LIBCPP_HIDE_FROM_ABI _Iter
+    operator()(_Iter __first, _Iter __middle, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const {
+      return __inplace_merge_impl(
+          std::move(__first), std::move(__middle), std::move(__last), std::move(__comp), std::move(__proj));
     }
 
     template <bidirectional_range _Range, class _Comp = ranges::less, class _Proj = identity>
-  requires sortable<iterator_t<_Range>, _Comp, _Proj>
-  _LIBCPP_HIDE_FROM_ABI
-  borrowed_iterator_t<_Range> operator()(_Range&& __range, iterator_t<_Range> __middle,
-                                            _Comp __comp = {}, _Proj __proj = {}) const {
-    // TODO: implement
-    (void)__range; (void)__middle; (void)__comp; (void)__proj;
-    return {};
+      requires sortable<
+          iterator_t<_Range>,
+          _Comp,
+          _Proj> _LIBCPP_HIDE_FROM_ABI borrowed_iterator_t<_Range>
+      operator()(_Range&& __range, iterator_t<_Range> __middle, _Comp __comp = {}, _Proj __proj = {}) const {
+      return __inplace_merge_impl(
+          ranges::begin(__range), std::move(__middle), ranges::end(__range), std::move(__comp), std::move(__proj));
     }
-
   };
 
 } // namespace __inplace_merge
 
 inline namespace __cpo {
   inline constexpr auto inplace_merge = __inplace_merge::__fn{};
 } // namespace __cpo
 } // namespace ranges
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
 #endif // _LIBCPP___ALGORITHM_RANGES_INPLACE_MERGE_H

libcxx/include/__algorithm/stable_sort.h

 //                                  move_iterator<value_type*>(__buff + __l2),
 //                                  move_iterator<_RandomAccessIterator>(__buff + __l2),
 //                                  move_iterator<_RandomAccessIterator>(__buff + __len),
 //                                  __first, __comp);
         return;
     }
     std::__stable_sort<_AlgPolicy, _Compare>(__first, __m, __comp, __l2, __buff, __buff_size);
     std::__stable_sort<_AlgPolicy, _Compare>(__m, __last, __comp, __len - __l2, __buff, __buff_size);
-    std::__inplace_merge<_AlgPolicy, _Compare>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size);
+    std::__inplace_merge<_AlgPolicy>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size);
 }
 
 template <class _AlgPolicy, class _RandomAccessIterator, class _Compare>
 inline _LIBCPP_HIDE_FROM_ABI
 void __stable_sort_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) {
   using value_type = typename iterator_traits<_RandomAccessIterator>::value_type;
   using difference_type = typename iterator_traits<_RandomAccessIterator>::difference_type;
 

libcxx/include/algorithm

template<input_range R1, input_range R2, class Pred = ranges::equal_to,
   template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
            weakly_incrementable O, class Comp = ranges::less,
            class Proj1 = identity, class Proj2 = identity>
     requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
     constexpr set_symmetric_difference_result<I1, I2, O>
       set_symmetric_difference(I1 first1, S1 last1, I2 first2, S2 last2, O result,
                                Comp comp = {}, Proj1 proj1 = {},
                                Proj2 proj2 = {});                                                   // since C++20
-  
   template<input_range R1, input_range R2, weakly_incrementable O,
            class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
     requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
     constexpr set_symmetric_difference_result<borrowed_iterator_t<R1>,
                                                       borrowed_iterator_t<R2>, O>
       set_symmetric_difference(R1&& r1, R2&& r2, O result, Comp comp = {},
                                Proj1 proj1 = {}, Proj2 proj2 = {});                                 // since C++20
 
   template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity,
            indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
     constexpr subrange<I>
       equal_range(I first, S last, const T& value, Comp comp = {}, Proj proj = {});                 // since C++20
-  
   template<forward_range R, class T, class Proj = identity,
            indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
              ranges::less>
     constexpr borrowed_subrange_t<R>
       equal_range(R&& r, const T& value, Comp comp = {}, Proj proj = {});                           // since C++20
-  
   template<class I1, class I2, class O>
     using set_union_result = in_in_out_result<I1, I2, O>;                                           // since C++20
 
   template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
            weakly_incrementable O, class Comp = ranges::less,
            class Proj1 = identity, class Proj2 = identity>
     requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
     constexpr set_union_result<I1, I2, O>
       set_union(I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = {},
                 Proj1 proj1 = {}, Proj2 proj2 = {});                                                // since C++20
 
   template<input_range R1, input_range R2, weakly_incrementable O,
            class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
     requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
     constexpr set_union_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
       set_union(R1&& r1, R2&& r2, O result, Comp comp = {},
                 Proj1 proj1 = {}, Proj2 proj2 = {});                                                // since C++20
 
   template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
            class Proj1 = identity, class Proj2 = identity,
            indirect_strict_weak_order<projected<I1, Proj1>, projected<I2, Proj2>> Comp =
              ranges::less>
     constexpr bool includes(I1 first1, S1 last1, I2 first2, S2 last2, Comp comp = {},
                             Proj1 proj1 = {}, Proj2 proj2 = {});                                   // Since C++20
-  
   template<input_range R1, input_range R2, class Proj1 = identity,
            class Proj2 = identity,
            indirect_strict_weak_order<projected<iterator_t<R1>, Proj1>,
                                       projected<iterator_t<R2>, Proj2>> Comp = ranges::less>
     constexpr bool includes(R1&& r1, R2&& r2, Comp comp = {},
                             Proj1 proj1 = {}, Proj2 proj2 = {});                                   // Since C++20
+
+  template<bidirectional_iterator I, sentinel_for<I> S, class Comp = ranges::less,
+           class Proj = identity>
+    requires sortable<I, Comp, Proj>
+    I inplace_merge(I first, I middle, S last, Comp comp = {}, Proj proj = {});                    // Since C++20
+
+  template<bidirectional_range R, class Comp = ranges::less, class Proj = identity>
+    requires sortable<iterator_t<R>, Comp, Proj>
+    borrowed_iterator_t<R>
+      inplace_merge(R&& r, iterator_t<R> middle, Comp comp = {},
+                    Proj proj = {});                                                               // Since C++20
 }
 
     constexpr bool     // constexpr in C++20
     all_of(InputIterator first, InputIterator last, Predicate pred);
 
 template <class InputIterator, class Predicate>
     constexpr bool     // constexpr in C++20
     any_of(InputIterator first, InputIterator last, Predicate pred);

 #include <__algorithm/ranges_fill_n.h>
 #include <__algorithm/ranges_find.h>
 #include <__algorithm/ranges_find_end.h>
 #include <__algorithm/ranges_find_first_of.h>
 #include <__algorithm/ranges_find_if.h>
 #include <__algorithm/ranges_find_if_not.h>
 #include <__algorithm/ranges_for_each.h>
 #include <__algorithm/ranges_for_each_n.h>
+#include <__algorithm/ranges_inplace_merge.h>
 #include <__algorithm/ranges_includes.h>
 #include <__algorithm/ranges_is_partitioned.h>
 #include <__algorithm/ranges_is_sorted.h>
 #include <__algorithm/ranges_is_sorted_until.h>
 #include <__algorithm/ranges_lexicographical_compare.h>
 #include <__algorithm/ranges_lower_bound.h>
 #include <__algorithm/ranges_make_heap.h>
 #include <__algorithm/ranges_max.h>

libcxx/include/module.modulemap.in

module std [system] {
 
   module algorithm {
     header "algorithm"
     export initializer_list
     export *
 
     module __algorithm {
       module adjacent_find                   { private header "__algorithm/adjacent_find.h" }
+      module algorithm_family                { private header "__algorithm/algorithm_family.h" }
       module all_of                          { private header "__algorithm/all_of.h" }
       module any_of                          { private header "__algorithm/any_of.h" }
       module binary_search                   { private header "__algorithm/binary_search.h" }
       module clamp                           { private header "__algorithm/clamp.h" }
       module comp                            { private header "__algorithm/comp.h" }
       module comp_ref_type                   { private header "__algorithm/comp_ref_type.h" }
       module copy                            { private header "__algorithm/copy.h" }
       module copy_backward                   { private header "__algorithm/copy_backward.h" }

libcxx/test/libcxx/private_headers.verify.cpp

for header in private_headers:
   ))
 
 END-SCRIPT
 */
 
 // DO NOT MANUALLY EDIT ANYTHING BETWEEN THE MARKERS BELOW
 // GENERATED-MARKER
 #include <__algorithm/adjacent_find.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/adjacent_find.h'}}
+#include <__algorithm/algorithm_family.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/algorithm_family.h'}}
 #include <__algorithm/all_of.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/all_of.h'}}
 #include <__algorithm/any_of.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/any_of.h'}}
 #include <__algorithm/binary_search.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/binary_search.h'}}
 #include <__algorithm/clamp.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/clamp.h'}}
 #include <__algorithm/comp.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/comp.h'}}
 #include <__algorithm/comp_ref_type.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/comp_ref_type.h'}}
 #include <__algorithm/copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/copy.h'}}
 #include <__algorithm/copy_backward.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/copy_backward.h'}}

libcxx/test/std/algorithms/alg.sorting/alg.merge/ranges_inplace_merge.pass.cpp

 #include <array>
 #include <concepts>
 #include <functional>
 #include <ranges>
 
 #include "almost_satisfies_types.h"
 #include "test_iterators.h"
 
-// TODO: SFINAE tests.
+template <
+    class Iter   = int*,
+    class Middle = int*,
+    class Sent   = int*,
+    class Comp   = std::ranges::less,
+    class Proj   = std::identity>
+concept HasInplaceMergeIter =
+    requires(Iter&& iter, Middle&& mid, Sent&& sent, Comp&& comp, Proj&& proj) {
+      std::ranges::inplace_merge(
+          std::forward<Iter>(iter),
+          std::forward<Middle>(mid),
+          std::forward<Sent>(sent),
+          std::forward<Comp>(comp),
+          std::forward<Proj>(proj));
+    };
+
+static_assert(HasInplaceMergeIter<int*, int*, int*>);
 
 constexpr bool test() {
   // TODO: main tests.
   // TODO: A custom comparator works.
   // TODO: A custom projection works.
 
   return true;
 }
 
 int main(int, char**) {
   test();
   static_assert(test());
 
   return 0;
 }

llvm/utils/gn/secondary/libcxx/include/BUILD.gn

values = [
       "requires_LIBCXX_ENABLE_THREADS=",
       "requires_LIBCXX_ENABLE_WIDE_CHARACTERS=",
     ]
   }
 
   copy("copy_headers") {
     sources = [
       "__algorithm/adjacent_find.h",
+      "__algorithm/algorithm_family.h",
       "__algorithm/all_of.h",
       "__algorithm/any_of.h",
       "__algorithm/binary_search.h",
       "__algorithm/clamp.h",
       "__algorithm/comp.h",
       "__algorithm/comp_ref_type.h",
       "__algorithm/copy.h",
       "__algorithm/copy_backward.h",