[libc++][PSTL] Implement std::merge

[philnik]

Add tests

[philnik]

Generate files

[ldionne]

libcxx/include/__algorithm/pstl_backends/cpu_backend.h

22

I think you forgot to document the new customization point here and also the __pstl one.

libcxx/include/__algorithm/pstl_backends/cpu_backends/merge.h

28

[ldionne]

This LGTM w/ comments and CI.

[philnik]

Address comments

[philnik]

Try to fix CI

[philnik]

Try to fix CI

[philnik]

Try to fix CI

libcxx/include/CMakeLists.txt

set(files
   __algorithm/pstl_any_all_none_of.h
   __algorithm/pstl_backend.h
   __algorithm/pstl_backends/cpu_backend.h
   __algorithm/pstl_backends/cpu_backends/any_of.h
   __algorithm/pstl_backends/cpu_backends/backend.h
   __algorithm/pstl_backends/cpu_backends/fill.h
   __algorithm/pstl_backends/cpu_backends/find_if.h
   __algorithm/pstl_backends/cpu_backends/for_each.h
+  __algorithm/pstl_backends/cpu_backends/merge.h
   __algorithm/pstl_backends/cpu_backends/serial.h
   __algorithm/pstl_backends/cpu_backends/thread.h
   __algorithm/pstl_backends/cpu_backends/transform.h
   __algorithm/pstl_copy.h
   __algorithm/pstl_fill.h
   __algorithm/pstl_find.h
   __algorithm/pstl_for_each.h
   __algorithm/pstl_frontend_dispatch.h
+  __algorithm/pstl_merge.h
   __algorithm/pstl_transform.h
   __algorithm/push_heap.h
   __algorithm/ranges_adjacent_find.h
   __algorithm/ranges_all_of.h
   __algorithm/ranges_any_of.h
   __algorithm/ranges_binary_search.h
   __algorithm/ranges_clamp.h
   __algorithm/ranges_copy.h

libcxx/include/__algorithm/pstl_backends/cpu_backend.h

 /*
 
   // _Functor takes a subrange for [__first, __last) that should be executed in serial
   template <class _RandomAccessIterator, class _Functor>
   void __parallel_for(_RandomAccessIterator __first, _RandomAccessIterator __last, _Functor __func);
 
   // Cancel the execution of other jobs - they aren't needed anymore
   void __cancel_execution();
 
   TODO: Document the parallel backend
 */
 
 #include <__algorithm/pstl_backends/cpu_backends/any_of.h>
 #include <__algorithm/pstl_backends/cpu_backends/fill.h>
 #include <__algorithm/pstl_backends/cpu_backends/find_if.h>
 #include <__algorithm/pstl_backends/cpu_backends/for_each.h>
+#include <__algorithm/pstl_backends/cpu_backends/merge.h>
 #include <__algorithm/pstl_backends/cpu_backends/transform.h>
 
 #endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKEND_H

libcxx/include/__algorithm/pstl_backends/cpu_backends/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_PSTL_BACKENDS_CPU_BACKENDS_MERGE_H
+#define _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_MERGE_H
+
+#include <__algorithm/merge.h>
+#include <__algorithm/pstl_backends/cpu_backends/backend.h>
+#include <__config>
+#include <__iterator/iterator_traits.h>
+#include <__type_traits/is_execution_policy.h>
+#include <__utility/terminate_on_exception.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template <class _ExecutionPolicy,
+          class _ForwardIterator1,
+          class _ForwardIterator2,
+          class _ForwatdOutIterator,
+          class _Comp>
+_LIBCPP_HIDE_FROM_ABI _ForwatdOutIterator __pstl_merge(
+    __cpu_backend_tag,
+    _ForwardIterator1 __first1,
+    _ForwardIterator1 __last1,
+    _ForwardIterator2 __first2,
+    _ForwardIterator2 __last2,
+    _ForwatdOutIterator __result,
+    _Comp __comp) {
+  if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
+                __has_random_access_iterator_category<_ForwardIterator1>::value &&
+                __has_random_access_iterator_category<_ForwardIterator2>::value &&
+                __has_random_access_iterator_category<_ForwatdOutIterator>::value) {
+    return std::__terminate_on_exception([&] {
+      __par_backend::__parallel_merge(
+          __first1,
+          __last1,
+          __first2,
+          __last2,
+          __result,
+          __comp,
+          [](_ForwardIterator1 __g_first1,
+             _ForwardIterator1 __g_last1,
+             _ForwardIterator2 __g_first2,
+             _ForwardIterator2 __g_last2,
+             _ForwatdOutIterator __g_result,
+             _Comp __g_comp) {
+            return std::__pstl_merge<__remove_parallel_policy_t<_ExecutionPolicy>>(
+                __cpu_backend_tag{},
+                std::move(__g_first1),
+                std::move(__g_last1),
+                std::move(__g_first2),
+                std::move(__g_last2),
+                std::move(__g_result),
+                std::move(__g_comp));
+          });
+      return __result + (__last1 - __first1) + (__last2 - __first2);
+    });
+  } else {
+    return std::merge(__first1, __last1, __first2, __last2, __result, __comp);
+  }
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_MERGE_H

libcxx/include/__algorithm/pstl_backends/cpu_backends/serial.h

 
 template <class _RandomAccessIterator, class _Fp>
 _LIBCPP_HIDE_FROM_ABI void __parallel_for(_RandomAccessIterator __first, _RandomAccessIterator __last, _Fp __f) {
   __f(__first, __last);
 }
 
 _LIBCPP_HIDE_FROM_ABI inline void __cancel_execution() {}
 
+template <class _RandomAccessIterator1,
+          class _RandomAccessIterator2,
+          class _RandomAccessIterator3,
+          class _Compare,
+          class _LeafMerge>
+_LIBCPP_HIDE_FROM_ABI void __parallel_merge(
+    _RandomAccessIterator1 __first1,
+    _RandomAccessIterator1 __last1,
+    _RandomAccessIterator2 __first2,
+    _RandomAccessIterator2 __last2,
+    _RandomAccessIterator3 __outit,
+    _Compare __comp,
+    _LeafMerge __leaf_merge) {
+  __leaf_merge(__first1, __last1, __first2, __last2, __outit, __comp);
+}
+
 // TODO: Complete this list
 
 } // namespace __serial_cpu_backend
 } // namespace __par_backend
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && && _LIBCPP_STD_VER >= 17
 
 #endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_SERIAL_H

libcxx/include/__algorithm/pstl_backends/cpu_backends/thread.h

 
 template <class _RandomAccessIterator, class _Fp>
 _LIBCPP_HIDE_FROM_ABI void __parallel_for(_RandomAccessIterator __first, _RandomAccessIterator __last, _Fp __f) {
   __f(__first, __last);
 }
 
 _LIBCPP_HIDE_FROM_ABI inline void __cancel_execution() {}
 
+template <class _RandomAccessIterator1,
+          class _RandomAccessIterator2,
+          class _RandomAccessIterator3,
+          class _Compare,
+          class _LeafMerge>
+_LIBCPP_HIDE_FROM_ABI void __parallel_merge(
+    _RandomAccessIterator1 __first1,
+    _RandomAccessIterator1 __last1,
+    _RandomAccessIterator2 __first2,
+    _RandomAccessIterator2 __last2,
+    _RandomAccessIterator3 __outit,
+    _Compare __comp,
+    _LeafMerge __leaf_merge) {
+  __leaf_merge(__first1, __last1, __first2, __last2, __outit, __comp);
+}
+
 } // namespace __thread_cpu_backend
 } // namespace __par_backend
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && && _LIBCPP_STD_VER >= 17
 
 #endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_THREAD_H

libcxx/include/__algorithm/pstl_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_PSTL_MERGE_H
+#define _LIBCPP___ALGORITHM_PSTL_MERGE_H
+
+#include <__algorithm/pstl_backend.h>
+#include <__config>
+#include <__type_traits/is_execution_policy.h>
+#include <__type_traits/remove_cvref.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+#if !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template <class _ExecutionPolicy,
+          class _ForwardIterator1,
+          class _ForwardIterator2,
+          class _ForwardOutIterator,
+          class _Comp                                         = std::less<>,
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+_ForwardOutIterator
+merge(_ExecutionPolicy&&,
+      _ForwardIterator1 __first1,
+      _ForwardIterator1 __last1,
+      _ForwardIterator2 __first2,
+      _ForwardIterator2 __last2,
+      _ForwardOutIterator __result,
+      _Comp __comp = {}) {
+  using _Backend = typename __select_backend<_RawPolicy>::type;
+  return std::__pstl_merge<_RawPolicy>(
+      _Backend{},
+      std::move(__first1),
+      std::move(__last1),
+      std::move(__first2),
+      std::move(__last2),
+      std::move(__result),
+      std::move(__comp));
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
+
+#endif // _LIBCPP___ALGORITHM_PSTL_MERGE_H

libcxx/include/__pstl/internal/algorithm_impl.h

return __internal::__remove_elements(
       __last,
       [&__pred](bool* __b, bool* __e, _RandomAccessIterator __it) {
         __internal::__brick_walk2(
             __b, __e, __it, [&__pred](bool& __x, _ReferenceType __y) { __x = !__pred(__y); }, _IsVector{});
       });
 }
 
 //------------------------------------------------------------------------
-// merge
-//------------------------------------------------------------------------
-
-template <class _ForwardIterator1, class _ForwardIterator2, class _OutputIterator, class _Compare>
-_OutputIterator __brick_merge(
-    _ForwardIterator1 __first1,
-    _ForwardIterator1 __last1,
-    _ForwardIterator2 __first2,
-    _ForwardIterator2 __last2,
-    _OutputIterator __d_first,
-    _Compare __comp,
-    /* __is_vector = */ std::false_type) noexcept {
-  return std::merge(__first1, __last1, __first2, __last2, __d_first, __comp);
-}
-
-template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _RandomAccessIterator3, class _Compare>
-_RandomAccessIterator3 __brick_merge(
-    _RandomAccessIterator1 __first1,
-    _RandomAccessIterator1 __last1,
-    _RandomAccessIterator2 __first2,
-    _RandomAccessIterator2 __last2,
-    _RandomAccessIterator3 __d_first,
-    _Compare __comp,
-    /* __is_vector = */ std::true_type) noexcept {
-  // TODO: vectorize
-  return std::merge(__first1, __last1, __first2, __last2, __d_first, __comp);
-}
-
-template <class _Tag,
-          class _ExecutionPolicy,
-          class _ForwardIterator1,
-          class _ForwardIterator2,
-          class _OutputIterator,
-          class _Compare>
-_OutputIterator __pattern_merge(
-    _Tag,
-    _ExecutionPolicy&&,
-    _ForwardIterator1 __first1,
-    _ForwardIterator1 __last1,
-    _ForwardIterator2 __first2,
-    _ForwardIterator2 __last2,
-    _OutputIterator __d_first,
-    _Compare __comp) noexcept {
-  return __internal::__brick_merge(
-      __first1, __last1, __first2, __last2, __d_first, __comp, typename _Tag::__is_vector{});
-}
-
-template <class _IsVector,
-          class _ExecutionPolicy,
-          class _RandomAccessIterator1,
-          class _RandomAccessIterator2,
-          class _RandomAccessIterator3,
-          class _Compare>
-_RandomAccessIterator3 __pattern_merge(
-    __parallel_tag<_IsVector> __tag,
-    _ExecutionPolicy&& __exec,
-    _RandomAccessIterator1 __first1,
-    _RandomAccessIterator1 __last1,
-    _RandomAccessIterator2 __first2,
-    _RandomAccessIterator2 __last2,
-    _RandomAccessIterator3 __d_first,
-    _Compare __comp) {
-  using __backend_tag = typename decltype(__tag)::__backend_tag;
-
-  __par_backend::__parallel_merge(
-      __backend_tag{},
-      std::forward<_ExecutionPolicy>(__exec),
-      __first1,
-      __last1,
-      __first2,
-      __last2,
-      __d_first,
-      __comp,
-      [](_RandomAccessIterator1 __f1,
-         _RandomAccessIterator1 __l1,
-         _RandomAccessIterator2 __f2,
-         _RandomAccessIterator2 __l2,
-         _RandomAccessIterator3 __f3,
-         _Compare __comp) { return __internal::__brick_merge(__f1, __l1, __f2, __l2, __f3, __comp, _IsVector{}); });
-  return __d_first + (__last1 - __first1) + (__last2 - __first2);
-}
-
-//------------------------------------------------------------------------
 // inplace_merge
 //------------------------------------------------------------------------
 template <class _BidirectionalIterator, class _Compare>
 void __brick_inplace_merge(
     _BidirectionalIterator __first,
     _BidirectionalIterator __middle,
     _BidirectionalIterator __last,
     _Compare __comp,

libcxx/include/__pstl/internal/glue_algorithm_impl.h

 template <class _ExecutionPolicy, class _ForwardIterator>
 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, bool>
 is_sorted(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last) {
   typedef typename std::iterator_traits<_ForwardIterator>::value_type _InputType;
   return std::is_sorted(std::forward<_ExecutionPolicy>(__exec), __first, __last, std::less<_InputType>());
 }
 
 // [alg.merge]
-template <class _ExecutionPolicy,
-          class _ForwardIterator1,
-          class _ForwardIterator2,
-          class _ForwardIterator,
-          class _Compare>
-__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator>
-merge(_ExecutionPolicy&& __exec,
-      _ForwardIterator1 __first1,
-      _ForwardIterator1 __last1,
-      _ForwardIterator2 __first2,
-      _ForwardIterator2 __last2,
-      _ForwardIterator __d_first,
-      _Compare __comp) {
-  auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first1, __first2, __d_first);
-
-  return __pstl::__internal::__pattern_merge(
-      __dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, __d_first, __comp);
-}
-
-template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _ForwardIterator>
-__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator>
-merge(_ExecutionPolicy&& __exec,
-      _ForwardIterator1 __first1,
-      _ForwardIterator1 __last1,
-      _ForwardIterator2 __first2,
-      _ForwardIterator2 __last2,
-      _ForwardIterator __d_first) {
-  return std::merge(
-      std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, __d_first, std::less<>());
-}
-
 template <class _ExecutionPolicy, class _BidirectionalIterator, class _Compare>
 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void>
 inplace_merge(_ExecutionPolicy&& __exec,
               _BidirectionalIterator __first,
               _BidirectionalIterator __middle,
               _BidirectionalIterator __last,
               _Compare __comp) {
   auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first);

libcxx/include/__pstl/internal/parallel_backend_serial.h

 template <class _ExecutionPolicy, typename _RandomAccessIterator, typename _Compare, typename _LeafSort>
 _LIBCPP_HIDE_FROM_ABI void
 __parallel_stable_sort(__pstl::__internal::__serial_backend_tag, _ExecutionPolicy&&, _RandomAccessIterator __first,
                        _RandomAccessIterator __last, _Compare __comp, _LeafSort __leaf_sort, std::size_t = 0)
 {
     __leaf_sort(__first, __last, __comp);
 }
 
-template <class _ExecutionPolicy, typename _RandomAccessIterator1, typename _RandomAccessIterator2,
-          typename _RandomAccessIterator3, typename _Compare, typename _LeafMerge>
-_LIBCPP_HIDE_FROM_ABI void
-__parallel_merge(__pstl::__internal::__serial_backend_tag, _ExecutionPolicy&&, _RandomAccessIterator1 __first1,
-                 _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2,
-                 _RandomAccessIterator3 __outit, _Compare __comp, _LeafMerge __leaf_merge)
-{
-    __leaf_merge(__first1, __last1, __first2, __last2, __outit, __comp);
-}
-
 template <class _ExecutionPolicy, typename _F1, typename _F2>
 _LIBCPP_HIDE_FROM_ABI void
 __parallel_invoke(__pstl::__internal::__serial_backend_tag, _ExecutionPolicy&&, _F1&& __f1, _F2&& __f2)
 {
     std::forward<_F1>(__f1)();
     std::forward<_F2>(__f2)();
 }
 
 } // namespace __serial_backend
 } // namespace __pstl
 
 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 #endif /* _PSTL_PARALLEL_BACKEND_SERIAL_H */

libcxx/include/algorithm

 #include <__algorithm/partition_point.h>
 #include <__algorithm/pop_heap.h>
 #include <__algorithm/prev_permutation.h>
 #include <__algorithm/pstl_any_all_none_of.h>
 #include <__algorithm/pstl_copy.h>
 #include <__algorithm/pstl_fill.h>
 #include <__algorithm/pstl_find.h>
 #include <__algorithm/pstl_for_each.h>
+#include <__algorithm/pstl_merge.h>
 #include <__algorithm/pstl_transform.h>
 #include <__algorithm/push_heap.h>
 #include <__algorithm/ranges_adjacent_find.h>
 #include <__algorithm/ranges_all_of.h>
 #include <__algorithm/ranges_any_of.h>
 #include <__algorithm/ranges_binary_search.h>
 #include <__algorithm/ranges_clamp.h>
 #include <__algorithm/ranges_copy.h>

libcxx/test/libcxx/private_headers.verify.cpp

 #include <__algorithm/pop_heap.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pop_heap.h'}}
 #include <__algorithm/prev_permutation.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/prev_permutation.h'}}
 #include <__algorithm/pstl_backends/cpu_backend.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pstl_backends/cpu_backend.h'}}
 #include <__algorithm/pstl_backends/cpu_backends/any_of.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pstl_backends/cpu_backends/any_of.h'}}
 #include <__algorithm/pstl_backends/cpu_backends/backend.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pstl_backends/cpu_backends/backend.h'}}
 #include <__algorithm/pstl_backends/cpu_backends/fill.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pstl_backends/cpu_backends/fill.h'}}
 #include <__algorithm/pstl_backends/cpu_backends/find_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pstl_backends/cpu_backends/find_if.h'}}
 #include <__algorithm/pstl_backends/cpu_backends/for_each.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pstl_backends/cpu_backends/for_each.h'}}
+#include <__algorithm/pstl_backends/cpu_backends/merge.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pstl_backends/cpu_backends/merge.h'}}
 #include <__algorithm/pstl_backends/cpu_backends/serial.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pstl_backends/cpu_backends/serial.h'}}
 #include <__algorithm/pstl_backends/cpu_backends/thread.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pstl_backends/cpu_backends/thread.h'}}
 #include <__algorithm/pstl_backends/cpu_backends/transform.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pstl_backends/cpu_backends/transform.h'}}
 #include <__algorithm/push_heap.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/push_heap.h'}}
 #include <__algorithm/ranges_adjacent_find.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_adjacent_find.h'}}
 #include <__algorithm/ranges_all_of.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_all_of.h'}}
 #include <__algorithm/ranges_any_of.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_any_of.h'}}
 #include <__algorithm/ranges_binary_search.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_binary_search.h'}}

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

+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14
+// UNSUPPORTED: libcpp-has-no-incomplete-pstl
+
+// template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
+//          class ForwardIterator>
+//   ForwardIterator
+//     merge(ExecutionPolicy&& exec,
+//           ForwardIterator1 first1, ForwardIterator1 last1,
+//           ForwardIterator2 first2, ForwardIterator2 last2,
+//           ForwardIterator result);
+//
+// template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
+//          class ForwardIterator, class Compare>
+//   ForwardIterator
+//     merge(ExecutionPolicy&& exec,
+//           ForwardIterator1 first1, ForwardIterator1 last1,
+//           ForwardIterator2 first2, ForwardIterator2 last2,
+//           ForwardIterator result, Compare comp);
+
+#include <algorithm>
+#include <array>
+#include <cassert>
+#include <iterator>
+#include <numeric>
+#include <vector>
+
+#include "type_algorithms.h"
+#include "test_execution_policies.h"
+#include "test_iterators.h"
+
+template <class Iter1, class Iter2>
+struct Test {
+  template <class Policy>
+  void operator()(Policy&& policy) {
+    { // simple test
+      int a[] = {1, 3, 5, 7, 9};
+      int b[] = {2, 4, 6, 8, 10};
+      std::array<int, std::size(a) + std::size(b)> out;
+      std::merge(
+          policy, Iter1(std::begin(a)), Iter1(std::end(a)), Iter2(std::begin(b)), Iter2(std::end(b)), std::begin(out));
+      assert((out == std::array{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}));
+    }
+
+    { // check that it works with the first range being empty
+      std::array<int, 0> a;
+      int b[] = {2, 4, 6, 8, 10};
+      std::array<int, std::size(a) + std::size(b)> out;
+      std::merge(
+          policy, Iter1(std::begin(a)), Iter1(std::end(a)), Iter2(std::begin(b)), Iter2(std::end(b)), std::begin(out));
+      assert((out == std::array{2, 4, 6, 8, 10}));
+    }
+
+    { // check that it works with the second range being empty
+      int a[] = {2, 4, 6, 8, 10};
+      std::array<int, 0> b;
+      std::array<int, std::size(a) + std::size(b)> out;
+      std::merge(
+          policy, Iter1(std::begin(a)), Iter1(std::end(a)), Iter2(std::begin(b)), Iter2(std::end(b)), std::begin(out));
+      assert((out == std::array{2, 4, 6, 8, 10}));
+    }
+
+    { // check that it works when the ranges don't have the same length
+      int a[] = {2, 4, 6, 8, 10};
+      int b[] = {3, 4};
+      std::array<int, std::size(a) + std::size(b)> out;
+      std::merge(
+          policy, Iter1(std::begin(a)), Iter1(std::end(a)), Iter2(std::begin(b)), Iter2(std::end(b)), std::begin(out));
+      assert((out == std::array{2, 3, 4, 4, 6, 8, 10}));
+    }
+
+    { // check that large ranges work
+      std::vector<int> a(100);
+      std::vector<int> b(100);
+      for (int i = 0; auto& e : a) {
+        e = i;
+        i += 2;
+      }
+
+      for (int i = 1; auto& e : b) {
+        e = i;
+        i += 2;
+      }
+
+      std::vector<int> out(std::size(a) + std::size(b));
+      std::merge(
+          Iter1(a.data()), Iter1(a.data() + a.size()), Iter2(b.data()), Iter2(b.data() + b.size()), std::begin(out));
+      std::vector<int> expected(200);
+      std::iota(expected.begin(), expected.end(), 0);
+      assert(std::equal(out.begin(), out.end(), expected.begin()));
+    }
+
+    { // check that the predicate is used
+      int a[] = {10, 9, 8, 7};
+      int b[] = {8, 4, 3};
+      std::array<int, std::size(a) + std::size(b)> out;
+      std::merge(
+          policy,
+          Iter1(std::begin(a)),
+          Iter1(std::end(a)),
+          Iter2(std::begin(b)),
+          Iter2(std::end(b)),
+          std::begin(out),
+          std::greater{});
+      assert((out == std::array{10, 9, 8, 8, 7, 4, 3}));
+    }
+  }
+};
+
+int main(int, char**) {
+  types::for_each(types::forward_iterator_list<int*>{}, types::apply_type_identity{[](auto v) {
+                    using Iter = typename decltype(v)::type;
+                    types::for_each(
+                        types::forward_iterator_list<int*>{},
+                        TestIteratorWithPolicies<types::partial_instantiation<Test, Iter>::template apply>{});
+                  }});
+
+  return 0;
+}