diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm
--- a/libcxx/include/algorithm
+++ b/libcxx/include/algorithm
@@ -367,20 +367,20 @@
     stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
 
 template <class RandomAccessIterator>
-    void
+    constexpr void                    // constexpr in C++20
     partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);
 
 template <class RandomAccessIterator, class Compare>
-    void
+    constexpr void                    // constexpr in C++20
     partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp);
 
 template <class InputIterator, class RandomAccessIterator>
-    RandomAccessIterator
+    constexpr RandomAccessIterator    // constexpr in C++20
     partial_sort_copy(InputIterator first, InputIterator last,
                       RandomAccessIterator result_first, RandomAccessIterator result_last);
 
 template <class InputIterator, class RandomAccessIterator, class Compare>
-    RandomAccessIterator
+    constexpr RandomAccessIterator    // constexpr in C++20
     partial_sort_copy(InputIterator first, InputIterator last,
                       RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp);
 
@@ -491,35 +491,35 @@
                              InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
 
 template <class RandomAccessIterator>
-    void
+    constexpr void                                   // constexpr in C++20
     push_heap(RandomAccessIterator first, RandomAccessIterator last);
 
 template <class RandomAccessIterator, class Compare>
-    void
+    constexpr void                                   // constexpr in C++20
     push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
 
 template <class RandomAccessIterator>
-    void
+    constexpr void                                   // constexpr in C++20
     pop_heap(RandomAccessIterator first, RandomAccessIterator last);
 
 template <class RandomAccessIterator, class Compare>
-    void
+    constexpr void                                   // constexpr in C++20
     pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
 
 template <class RandomAccessIterator>
-    void
+    constexpr void                                   // constexpr in C++20
     make_heap(RandomAccessIterator first, RandomAccessIterator last);
 
 template <class RandomAccessIterator, class Compare>
-    void
+    constexpr void                                   // constexpr in C++20
     make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
 
 template <class RandomAccessIterator>
-    void
+    constexpr void                                   // constexpr in C++20
     sort_heap(RandomAccessIterator first, RandomAccessIterator last);
 
 template <class RandomAccessIterator, class Compare>
-    void
+    constexpr void                                   // constexpr in C++20
     sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
 
 template <class RandomAccessIterator>
@@ -5000,7 +5000,7 @@
 // push_heap
 
 template <class _Compare, class _RandomAccessIterator>
-void
+_LIBCPP_CONSTEXPR_AFTER_CXX11 void
 __sift_up(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
           typename iterator_traits<_RandomAccessIterator>::difference_type __len)
 {
@@ -5027,7 +5027,7 @@
 }
 
 template <class _RandomAccessIterator, class _Compare>
-inline _LIBCPP_INLINE_VISIBILITY
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 void
 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
 {
@@ -5036,7 +5036,7 @@
 }
 
 template <class _RandomAccessIterator>
-inline _LIBCPP_INLINE_VISIBILITY
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 void
 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 {
@@ -5046,7 +5046,7 @@
 // pop_heap
 
 template <class _Compare, class _RandomAccessIterator>
-void
+_LIBCPP_CONSTEXPR_AFTER_CXX11 void
 __sift_down(_RandomAccessIterator __first, _RandomAccessIterator /*__last*/,
             _Compare __comp,
             typename iterator_traits<_RandomAccessIterator>::difference_type __len,
@@ -5078,7 +5078,7 @@
     value_type __top(_VSTD::move(*__start));
     do
     {
-        // we are not in heap-order, swap the parent with it's largest child
+        // we are not in heap-order, swap the parent with its largest child
         *__start = _VSTD::move(*__child_i);
         __start = __child_i;
 
@@ -5101,7 +5101,7 @@
 }
 
 template <class _Compare, class _RandomAccessIterator>
-inline _LIBCPP_INLINE_VISIBILITY
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 void
 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
            typename iterator_traits<_RandomAccessIterator>::difference_type __len)
@@ -5114,7 +5114,7 @@
 }
 
 template <class _RandomAccessIterator, class _Compare>
-inline _LIBCPP_INLINE_VISIBILITY
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 void
 pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
 {
@@ -5123,7 +5123,7 @@
 }
 
 template <class _RandomAccessIterator>
-inline _LIBCPP_INLINE_VISIBILITY
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 void
 pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 {
@@ -5133,7 +5133,7 @@
 // make_heap
 
 template <class _Compare, class _RandomAccessIterator>
-void
+_LIBCPP_CONSTEXPR_AFTER_CXX11 void
 __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
 {
     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
@@ -5149,7 +5149,7 @@
 }
 
 template <class _RandomAccessIterator, class _Compare>
-inline _LIBCPP_INLINE_VISIBILITY
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 void
 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
 {
@@ -5158,7 +5158,7 @@
 }
 
 template <class _RandomAccessIterator>
-inline _LIBCPP_INLINE_VISIBILITY
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 void
 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 {
@@ -5168,7 +5168,7 @@
 // sort_heap
 
 template <class _Compare, class _RandomAccessIterator>
-void
+_LIBCPP_CONSTEXPR_AFTER_CXX17 void
 __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
 {
     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
@@ -5177,7 +5177,7 @@
 }
 
 template <class _RandomAccessIterator, class _Compare>
-inline _LIBCPP_INLINE_VISIBILITY
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 void
 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
 {
@@ -5186,7 +5186,7 @@
 }
 
 template <class _RandomAccessIterator>
-inline _LIBCPP_INLINE_VISIBILITY
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 void
 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 {
@@ -5196,7 +5196,7 @@
 // partial_sort
 
 template <class _Compare, class _RandomAccessIterator>
-void
+_LIBCPP_CONSTEXPR_AFTER_CXX17 void
 __partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
              _Compare __comp)
 {
@@ -5214,7 +5214,7 @@
 }
 
 template <class _RandomAccessIterator, class _Compare>
-inline _LIBCPP_INLINE_VISIBILITY
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 void
 partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
              _Compare __comp)
@@ -5224,7 +5224,7 @@
 }
 
 template <class _RandomAccessIterator>
-inline _LIBCPP_INLINE_VISIBILITY
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 void
 partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)
 {
@@ -5235,7 +5235,7 @@
 // partial_sort_copy
 
 template <class _Compare, class _InputIterator, class _RandomAccessIterator>
-_RandomAccessIterator
+_LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator
 __partial_sort_copy(_InputIterator __first, _InputIterator __last,
                     _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp)
 {
@@ -5258,7 +5258,7 @@
 }
 
 template <class _InputIterator, class _RandomAccessIterator, class _Compare>
-inline _LIBCPP_INLINE_VISIBILITY
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 _RandomAccessIterator
 partial_sort_copy(_InputIterator __first, _InputIterator __last,
                   _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp)
@@ -5268,7 +5268,7 @@
 }
 
 template <class _InputIterator, class _RandomAccessIterator>
-inline _LIBCPP_INLINE_VISIBILITY
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 _RandomAccessIterator
 partial_sort_copy(_InputIterator __first, _InputIterator __last,
                   _RandomAccessIterator __result_first, _RandomAccessIterator __result_last)
diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/make.heap/make_heap.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/make.heap/make_heap.pass.cpp
--- a/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/make.heap/make_heap.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/make.heap/make_heap.pass.cpp
@@ -10,43 +10,57 @@
 
 // template<RandomAccessIterator Iter>
 //   requires ShuffleIterator<Iter> && LessThanComparable<Iter::value_type>
-//   void
+//   constexpr void  // constexpr in C++20
 //   make_heap(Iter first, Iter last);
 
 #include <algorithm>
-#include <random>
 #include <cassert>
 
 #include "test_macros.h"
 #include "test_iterators.h"
+#include "MoveOnly.h"
 
-std::mt19937 randomness;
-
-void test(int N)
+template<class T, class Iter>
+TEST_CONSTEXPR_CXX20 bool test()
 {
-    int* ia = new int [N];
-    for (int i = 0; i < N; ++i)
-        ia[i] = i;
-    std::shuffle(ia, ia+N, randomness);
-    std::make_heap(ia, ia+N);
-    assert(std::is_heap(ia, ia+N));
-
-    typedef random_access_iterator<int *> RI;
-    std::shuffle(RI(ia), RI(ia+N), randomness);
-    std::make_heap(RI(ia), RI(ia+N));
-    assert(std::is_heap(RI(ia), RI(ia+N)));
-
-    delete [] ia;
+    int orig[15] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
+    T work[15] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
+    for (int n = 0; n < 15; ++n) {
+        std::make_heap(Iter(work), Iter(work+n));
+        assert(std::is_heap(work, work+n));
+        assert(std::is_permutation(work, work+n, orig));
+        std::copy(orig, orig+n, work);
+    }
+
+    {
+        T input[] = {3, 4, 1, 2, 5};
+        std::make_heap(Iter(input), Iter(input + 5));
+        assert(std::is_heap(input, input + 5));
+        std::pop_heap(input, input + 5); assert(input[4] == 5);
+        std::pop_heap(input, input + 4); assert(input[3] == 4);
+        std::pop_heap(input, input + 3); assert(input[2] == 3);
+        std::pop_heap(input, input + 2); assert(input[1] == 2);
+        std::pop_heap(input, input + 1); assert(input[0] == 1);
+    }
+    return true;
 }
 
 int main(int, char**)
 {
-    test(0);
-    test(1);
-    test(2);
-    test(3);
-    test(10);
-    test(1000);
-
-  return 0;
+    test<int, random_access_iterator<int*> >();
+    test<int, int*>();
+
+#if TEST_STD_VER >= 11
+    test<MoveOnly, random_access_iterator<MoveOnly*>>();
+    test<MoveOnly, MoveOnly*>();
+#endif
+
+#if TEST_STD_VER >= 20
+    static_assert(test<int, random_access_iterator<int*>>());
+    static_assert(test<int, int*>());
+    static_assert(test<MoveOnly, random_access_iterator<MoveOnly*>>());
+    static_assert(test<MoveOnly, MoveOnly*>());
+#endif
+
+    return 0;
 }
diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/make.heap/make_heap_comp.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/make.heap/make_heap_comp.pass.cpp
--- a/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/make.heap/make_heap_comp.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/make.heap/make_heap_comp.pass.cpp
@@ -8,101 +8,60 @@
 
 // <algorithm>
 
-// template<RandomAccessIterator Iter, StrictWeakOrder<auto, Iter::value_type> Compare>
-//   requires ShuffleIterator<Iter> && CopyConstructible<Compare>
-//   void
+// template<RandomAccessIterator Iter>
+//   requires ShuffleIterator<Iter> && LessThanComparable<Iter::value_type>
+//   constexpr void  // constexpr in C++20
 //   make_heap(Iter first, Iter last, Compare comp);
 
 #include <algorithm>
-#include <functional>
-#include <memory>
-#include <random>
 #include <cassert>
+#include <functional>
 
 #include "test_macros.h"
-#include "counting_predicates.h"
 #include "test_iterators.h"
+#include "MoveOnly.h"
 
-struct indirect_less
-{
-    template <class P>
-    bool operator()(const P& x, const P& y)
-        {return *x < *y;}
-};
-
-std::mt19937 randomness;
-
-void test(int N)
+template<class T, class Iter>
+TEST_CONSTEXPR_CXX20 bool test()
 {
-    int* ia = new int [N];
-    {
-    for (int i = 0; i < N; ++i)
-        ia[i] = i;
-    std::shuffle(ia, ia+N, randomness);
-    std::make_heap(ia, ia+N, std::greater<int>());
-    assert(std::is_heap(ia, ia+N, std::greater<int>()));
-
-    std::shuffle(ia, ia+N, randomness);
-    std::make_heap(random_access_iterator<int *>(ia),
-                   random_access_iterator<int *>(ia+N), std::greater<int>());
-    assert(std::is_heap(ia, ia+N, std::greater<int>()));
-    }
-
-//  Ascending
-    {
-    binary_counting_predicate<std::greater<int>, int, int> pred ((std::greater<int>()));
-    for (int i = 0; i < N; ++i)
-        ia[i] = i;
-    std::make_heap(ia, ia+N, std::ref(pred));
-    assert(pred.count() <= 3u*N);
-    assert(std::is_heap(ia, ia+N, pred));
+    int orig[15] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
+    T work[15] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
+    for (int n = 0; n < 15; ++n) {
+        std::make_heap(Iter(work), Iter(work+n), std::greater<T>());
+        assert(std::is_heap(work, work+n, std::greater<T>()));
+        assert(std::is_permutation(work, work+n, orig));
+        std::copy(orig, orig+n, work);
     }
 
-//  Descending
     {
-    binary_counting_predicate<std::greater<int>, int, int> pred ((std::greater<int>()));
-    for (int i = 0; i < N; ++i)
-        ia[N-1-i] = i;
-    std::make_heap(ia, ia+N, std::ref(pred));
-    assert(pred.count() <= 3u*N);
-    assert(std::is_heap(ia, ia+N, pred));
+        T input[] = {3, 4, 1, 2, 5};
+        std::make_heap(Iter(input), Iter(input + 5), std::greater<T>());
+        assert(std::is_heap(input, input + 5, std::greater<T>()));
+        std::pop_heap(input, input + 5, std::greater<T>()); assert(input[4] == 1);
+        std::pop_heap(input, input + 4, std::greater<T>()); assert(input[3] == 2);
+        std::pop_heap(input, input + 3, std::greater<T>()); assert(input[2] == 3);
+        std::pop_heap(input, input + 2, std::greater<T>()); assert(input[1] == 4);
+        std::pop_heap(input, input + 1, std::greater<T>()); assert(input[0] == 5);
     }
-
-//  Random
-    {
-    binary_counting_predicate<std::greater<int>, int, int> pred ((std::greater<int>()));
-    std::shuffle(ia, ia+N, randomness);
-    std::make_heap(ia, ia+N, std::ref(pred));
-    assert(pred.count() <= 3u*N);
-    assert(std::is_heap(ia, ia+N, pred));
-    }
-
-    delete [] ia;
+    return true;
 }
 
 int main(int, char**)
 {
-    test(0);
-    test(1);
-    test(2);
-    test(3);
-    test(10);
-    test(1000);
-    test(10000);
-    test(100000);
+    test<int, random_access_iterator<int*> >();
+    test<int, int*>();
 
 #if TEST_STD_VER >= 11
-    {
-    const int N = 1000;
-    std::unique_ptr<int>* ia = new std::unique_ptr<int> [N];
-    for (int i = 0; i < N; ++i)
-        ia[i].reset(new int(i));
-    std::shuffle(ia, ia+N, randomness);
-    std::make_heap(ia, ia+N, indirect_less());
-    assert(std::is_heap(ia, ia+N, indirect_less()));
-    delete [] ia;
-    }
+    test<MoveOnly, random_access_iterator<MoveOnly*>>();
+    test<MoveOnly, MoveOnly*>();
+#endif
+
+#if TEST_STD_VER >= 20
+    static_assert(test<int, random_access_iterator<int*>>());
+    static_assert(test<int, int*>());
+    static_assert(test<MoveOnly, random_access_iterator<MoveOnly*>>());
+    static_assert(test<MoveOnly, MoveOnly*>());
 #endif
 
-  return 0;
+    return 0;
 }
diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/pop.heap/pop_heap.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/pop.heap/pop_heap.pass.cpp
--- a/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/pop.heap/pop_heap.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/pop.heap/pop_heap.pass.cpp
@@ -10,49 +10,59 @@
 
 // template<RandomAccessIterator Iter>
 //   requires ShuffleIterator<Iter> && LessThanComparable<Iter::value_type>
-//   void
+//   constexpr void  // constexpr in C++20
 //   pop_heap(Iter first, Iter last);
 
 #include <algorithm>
-#include <random>
 #include <cassert>
+#include <functional>
 
 #include "test_macros.h"
 #include "test_iterators.h"
+#include "MoveOnly.h"
 
-std::mt19937 randomness;
-
-void test(int N)
+template<class T, class Iter>
+TEST_CONSTEXPR_CXX20 bool test()
 {
-    int* ia = new int [N];
-    for (int i = 0; i < N; ++i)
-        ia[i] = i;
-    std::shuffle(ia, ia+N, randomness);
-    std::make_heap(ia, ia+N);
-    for (int i = N; i > 0; --i)
-    {
-        std::pop_heap(ia, ia+i);
-        assert(std::is_heap(ia, ia+i-1));
+    T orig[15] = {9,6,9,5,5, 8,9,1,1,3, 5,3,4,7,2};
+    T work[15] = {9,6,9,5,5, 8,9,1,1,3, 5,3,4,7,2};
+    assert(std::is_heap(orig, orig+15));
+    for (int i = 15; i >= 1; --i) {
+        std::pop_heap(Iter(work), Iter(work+i));
+        assert(std::is_heap(work, work+i-1));
+        assert(std::max_element(work, work+i-1) == work);
+        assert(std::is_permutation(work, work+15, orig));
     }
-    std::pop_heap(ia, ia);
-
+    assert(std::is_sorted(work, work+15));
 
-    typedef random_access_iterator<int *> RI;
-    std::shuffle(RI(ia), RI(ia+N), randomness);
-    std::make_heap(RI(ia), RI(ia+N));
-    for (int i = N; i > 0; --i)
     {
-        std::pop_heap(RI(ia), RI(ia+i));
-        assert(std::is_heap(RI(ia), RI(ia+i-1)));
+        T input[] = {5, 4, 1, 2, 3};
+        assert(std::is_heap(input, input + 5));
+        std::pop_heap(Iter(input), Iter(input + 5)); assert(input[4] == 5);
+        std::pop_heap(Iter(input), Iter(input + 4)); assert(input[3] == 4);
+        std::pop_heap(Iter(input), Iter(input + 3)); assert(input[2] == 3);
+        std::pop_heap(Iter(input), Iter(input + 2)); assert(input[1] == 2);
+        std::pop_heap(Iter(input), Iter(input + 1)); assert(input[0] == 1);
     }
-    std::pop_heap(RI(ia), RI(ia));
-
-    delete [] ia;
+    return true;
 }
 
 int main(int, char**)
 {
-    test(1000);
+    test<int, random_access_iterator<int*> >();
+    test<int, int*>();
+
+#if TEST_STD_VER >= 11
+    test<MoveOnly, random_access_iterator<MoveOnly*>>();
+    test<MoveOnly, MoveOnly*>();
+#endif
+
+#if TEST_STD_VER >= 20
+    static_assert(test<int, random_access_iterator<int*>>());
+    static_assert(test<int, int*>());
+    static_assert(test<MoveOnly, random_access_iterator<MoveOnly*>>());
+    static_assert(test<MoveOnly, MoveOnly*>());
+#endif
 
-  return 0;
+    return 0;
 }
diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/pop.heap/pop_heap_comp.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/pop.heap/pop_heap_comp.pass.cpp
--- a/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/pop.heap/pop_heap_comp.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/pop.heap/pop_heap_comp.pass.cpp
@@ -8,77 +8,61 @@
 
 // <algorithm>
 
-// template<RandomAccessIterator Iter, StrictWeakOrder<auto, Iter::value_type> Compare>
-//   requires ShuffleIterator<Iter> && CopyConstructible<Compare>
-//   void
+// template<RandomAccessIterator Iter>
+//   requires ShuffleIterator<Iter> && LessThanComparable<Iter::value_type>
+//   constexpr void  // constexpr in C++20
 //   pop_heap(Iter first, Iter last, Compare comp);
 
 #include <algorithm>
-#include <functional>
-#include <random>
 #include <cassert>
-#include <memory>
+#include <functional>
 
 #include "test_macros.h"
 #include "test_iterators.h"
+#include "MoveOnly.h"
 
-struct indirect_less
+template<class T, class Iter>
+TEST_CONSTEXPR_CXX20 bool test()
 {
-    template <class P>
-    bool operator()(const P& x, const P& y)
-        {return *x < *y;}
-};
-
-
-std::mt19937 randomness;
-
-void test(int N)
-{
-    int* ia = new int [N];
-    for (int i = 0; i < N; ++i)
-        ia[i] = i;
-    std::shuffle(ia, ia+N, randomness);
-    std::make_heap(ia, ia+N, std::greater<int>());
-    for (int i = N; i > 0; --i)
-    {
-        std::pop_heap(ia, ia+i, std::greater<int>());
-        assert(std::is_heap(ia, ia+i-1, std::greater<int>()));
+    T orig[15] = {1,1,2,3,3, 8,4,6,5,5, 5,9,9,7,9};
+    T work[15] = {1,1,2,3,3, 8,4,6,5,5, 5,9,9,7,9};
+    assert(std::is_heap(orig, orig+15, std::greater<T>()));
+    for (int i = 15; i >= 1; --i) {
+        std::pop_heap(Iter(work), Iter(work+i), std::greater<T>());
+        assert(std::is_heap(work, work+i-1, std::greater<T>()));
+        assert(std::min_element(work, work+i-1) == work);
+        assert(std::is_permutation(work, work+15, orig));
     }
-    std::pop_heap(ia, ia, std::greater<int>());
+    assert(std::is_sorted(work, work+15, std::greater<T>()));
 
-    typedef random_access_iterator<int *> RI;
-    std::shuffle(RI(ia), RI(ia+N), randomness);
-    std::make_heap(RI(ia), RI(ia+N), std::greater<int>());
-    for (int i = N; i > 0; --i)
     {
-        std::pop_heap(RI(ia), RI(ia+i), std::greater<int>());
-        assert(std::is_heap(RI(ia), RI(ia+i-1), std::greater<int>()));
+        T input[] = {1, 2, 5, 4, 3};
+        assert(std::is_heap(input, input + 5, std::greater<T>()));
+        std::pop_heap(Iter(input), Iter(input + 5), std::greater<T>()); assert(input[4] == 1);
+        std::pop_heap(Iter(input), Iter(input + 4), std::greater<T>()); assert(input[3] == 2);
+        std::pop_heap(Iter(input), Iter(input + 3), std::greater<T>()); assert(input[2] == 3);
+        std::pop_heap(Iter(input), Iter(input + 2), std::greater<T>()); assert(input[1] == 4);
+        std::pop_heap(Iter(input), Iter(input + 1), std::greater<T>()); assert(input[0] == 5);
     }
-    std::pop_heap(RI(ia), RI(ia), std::greater<int>());
-
-    delete [] ia;
+    return true;
 }
 
 int main(int, char**)
 {
-    test(1000);
+    test<int, random_access_iterator<int*> >();
+    test<int, int*>();
 
 #if TEST_STD_VER >= 11
-    {
-    const int N = 1000;
-    std::unique_ptr<int>* ia = new std::unique_ptr<int> [N];
-    for (int i = 0; i < N; ++i)
-        ia[i].reset(new int(i));
-    std::shuffle(ia, ia+N, randomness);
-    std::make_heap(ia, ia+N, indirect_less());
-    for (int i = N; i > 0; --i)
-    {
-        std::pop_heap(ia, ia+i, indirect_less());
-        assert(std::is_heap(ia, ia+i-1, indirect_less()));
-    }
-    delete [] ia;
-    }
+    test<MoveOnly, random_access_iterator<MoveOnly*>>();
+    test<MoveOnly, MoveOnly*>();
+#endif
+
+#if TEST_STD_VER >= 20
+    static_assert(test<int, random_access_iterator<int*>>());
+    static_assert(test<int, int*>());
+    static_assert(test<MoveOnly, random_access_iterator<MoveOnly*>>());
+    static_assert(test<MoveOnly, MoveOnly*>());
 #endif
 
-  return 0;
+    return 0;
 }
diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/push.heap/push_heap.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/push.heap/push_heap.pass.cpp
--- a/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/push.heap/push_heap.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/push.heap/push_heap.pass.cpp
@@ -9,46 +9,57 @@
 // <algorithm>
 
 // template<RandomAccessIterator Iter>
-//   requires ShuffleIterator<Iter>
-//         && LessThanComparable<Iter::value_type>
-//   void
+//   requires ShuffleIterator<Iter> && LessThanComparable<Iter::value_type>
+//   constexpr void  // constexpr in C++20
 //   push_heap(Iter first, Iter last);
 
 #include <algorithm>
-#include <random>
 #include <cassert>
+#include <functional>
 
 #include "test_macros.h"
 #include "test_iterators.h"
+#include "MoveOnly.h"
 
-std::mt19937 randomness;
-
-void test(int N)
+template<class T, class Iter>
+TEST_CONSTEXPR_CXX20 bool test()
 {
-    int* ia = new int [N];
-    for (int i = 0; i < N; ++i)
-        ia[i] = i;
-    std::shuffle(ia, ia+N, randomness);
-    for (int i = 0; i <= N; ++i)
-    {
-        std::push_heap(ia, ia+i);
-        assert(std::is_heap(ia, ia+i));
+    T orig[15] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
+    T work[15] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
+    for (int i = 1; i < 15; ++i) {
+        std::push_heap(Iter(work), Iter(work+i));
+        assert(std::is_permutation(work, work+i, orig));
+        assert(std::is_heap(work, work+i));
     }
 
-    typedef random_access_iterator<int *> RI;
-    std::shuffle(RI(ia), RI(ia+N), randomness);
-    for (int i = 0; i <= N; ++i)
     {
-        std::push_heap(RI(ia), RI(ia+i));
-        assert(std::is_heap(RI(ia), RI(ia+i)));
+        T input[] = {1, 3, 2, 5, 4};
+        std::push_heap(Iter(input), Iter(input + 1)); assert(input[0] == 1);
+        std::push_heap(Iter(input), Iter(input + 2)); assert(input[0] == 3);
+        std::push_heap(Iter(input), Iter(input + 3)); assert(input[0] == 3);
+        std::push_heap(Iter(input), Iter(input + 4)); assert(input[0] == 5);
+        std::push_heap(Iter(input), Iter(input + 5)); assert(input[0] == 5);
+        assert(std::is_heap(input, input + 5));
     }
-
-    delete [] ia;
+    return true;
 }
 
 int main(int, char**)
 {
-    test(1000);
+    test<int, random_access_iterator<int*> >();
+    test<int, int*>();
+
+#if TEST_STD_VER >= 11
+    test<MoveOnly, random_access_iterator<MoveOnly*>>();
+    test<MoveOnly, MoveOnly*>();
+#endif
+
+#if TEST_STD_VER >= 20
+    static_assert(test<int, random_access_iterator<int*>>());
+    static_assert(test<int, int*>());
+    static_assert(test<MoveOnly, random_access_iterator<MoveOnly*>>());
+    static_assert(test<MoveOnly, MoveOnly*>());
+#endif
 
-  return 0;
+    return 0;
 }
diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/push.heap/push_heap_comp.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/push.heap/push_heap_comp.pass.cpp
--- a/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/push.heap/push_heap_comp.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/push.heap/push_heap_comp.pass.cpp
@@ -9,71 +9,57 @@
 // <algorithm>
 
 // template<RandomAccessIterator Iter>
-//   requires ShuffleIterator<Iter>
-//         && LessThanComparable<Iter::value_type>
-//   void
+//   requires ShuffleIterator<Iter> && LessThanComparable<Iter::value_type>
+//   constexpr void  // constexpr in C++20
 //   push_heap(Iter first, Iter last);
 
 #include <algorithm>
-#include <functional>
-#include <random>
 #include <cassert>
-#include <memory>
+#include <functional>
 
 #include "test_macros.h"
 #include "test_iterators.h"
+#include "MoveOnly.h"
 
-struct indirect_less
+template<class T, class Iter>
+TEST_CONSTEXPR_CXX20 bool test()
 {
-    template <class P>
-    bool operator()(const P& x, const P& y)
-        {return *x < *y;}
-};
-
-std::mt19937 randomness;
-
-void test(int N)
-{
-    int* ia = new int [N];
-    for (int i = 0; i < N; ++i)
-        ia[i] = i;
-    std::shuffle(ia, ia+N, randomness);
-    for (int i = 0; i <= N; ++i)
-    {
-        std::push_heap(ia, ia+i, std::greater<int>());
-        assert(std::is_heap(ia, ia+i, std::greater<int>()));
+    T orig[15] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
+    T work[15] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
+    for (int i = 1; i < 15; ++i) {
+        std::push_heap(Iter(work), Iter(work+i), std::greater<T>());
+        assert(std::is_permutation(work, work+i, orig));
+        assert(std::is_heap(work, work+i, std::greater<T>()));
     }
 
-    typedef random_access_iterator<int *> RI;
-    std::shuffle(RI(ia), RI(ia+N), randomness);
-    for (int i = 0; i <= N; ++i)
     {
-        std::push_heap(RI(ia), RI(ia+i), std::greater<int>());
-        assert(std::is_heap(RI(ia), RI(ia+i), std::greater<int>()));
+        T input[] = {5, 3, 4, 1, 2};
+        std::push_heap(Iter(input), Iter(input + 1), std::greater<T>()); assert(input[0] == 5);
+        std::push_heap(Iter(input), Iter(input + 2), std::greater<T>()); assert(input[0] == 3);
+        std::push_heap(Iter(input), Iter(input + 3), std::greater<T>()); assert(input[0] == 3);
+        std::push_heap(Iter(input), Iter(input + 4), std::greater<T>()); assert(input[0] == 1);
+        std::push_heap(Iter(input), Iter(input + 5), std::greater<T>()); assert(input[0] == 1);
+        assert(std::is_heap(input, input + 5, std::greater<T>()));
     }
-
-    delete [] ia;
+    return true;
 }
 
 int main(int, char**)
 {
-    test(1000);
+    test<int, random_access_iterator<int*> >();
+    test<int, int*>();
 
 #if TEST_STD_VER >= 11
-    {
-    const int N = 1000;
-    std::unique_ptr<int>* ia = new std::unique_ptr<int> [N];
-    for (int i = 0; i < N; ++i)
-        ia[i].reset(new int(i));
-    std::shuffle(ia, ia+N, randomness);
-    for (int i = 0; i <= N; ++i)
-    {
-        std::push_heap(ia, ia+i, indirect_less());
-        assert(std::is_heap(ia, ia+i, indirect_less()));
-    }
-    delete [] ia;
-    }
+    test<MoveOnly, random_access_iterator<MoveOnly*>>();
+    test<MoveOnly, MoveOnly*>();
+#endif
+
+#if TEST_STD_VER >= 20
+    static_assert(test<int, random_access_iterator<int*>>());
+    static_assert(test<int, int*>());
+    static_assert(test<MoveOnly, random_access_iterator<MoveOnly*>>());
+    static_assert(test<MoveOnly, MoveOnly*>());
 #endif
 
-  return 0;
+    return 0;
 }
diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/sort.heap/sort_heap.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/sort.heap/sort_heap.pass.cpp
--- a/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/sort.heap/sort_heap.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/sort.heap/sort_heap.pass.cpp
@@ -10,45 +10,61 @@
 
 // template<RandomAccessIterator Iter>
 //   requires ShuffleIterator<Iter> && LessThanComparable<Iter::value_type>
-//   void
+//   constexpr void  // constexpr in C++20
 //   sort_heap(Iter first, Iter last);
 
 #include <algorithm>
-#include <random>
 #include <cassert>
 
 #include "test_macros.h"
 #include "test_iterators.h"
 
-std::mt19937 randomness;
+#include "test_macros.h"
+#include "test_iterators.h"
+#include "MoveOnly.h"
 
-void test(int N)
+template<class T, class Iter>
+TEST_CONSTEXPR_CXX20 bool test()
 {
-    int* ia = new int [N];
-    for (int i = 0; i < N; ++i)
-        ia[i] = i;
-    std::shuffle(ia, ia+N, randomness);
-    std::make_heap(ia, ia+N);
-    std::sort_heap(ia, ia+N);
-    assert(std::is_sorted(ia, ia+N));
-
-    typedef random_access_iterator<int *> RI;
-    std::shuffle(RI(ia), RI(ia+N), randomness);
-    std::make_heap(RI(ia), RI(ia+N));
-    std::sort_heap(RI(ia), RI(ia+N));
-    assert(std::is_sorted(RI(ia), RI(ia+N)));
-
-    delete [] ia;
+    int orig[15] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
+    T work[15] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
+    for (int n = 0; n < 15; ++n) {
+        std::make_heap(work, work+n);
+        std::sort_heap(Iter(work), Iter(work+n));
+        assert(std::is_sorted(work, work+n));
+        assert(std::is_permutation(work, work+n, orig));
+        std::copy(orig, orig+n, work);
+    }
+
+    {
+        T input[] = {5, 3, 4, 1, 2};
+        assert(std::is_heap(input, input + 5));
+        std::sort_heap(Iter(input), Iter(input + 5));
+        assert(input[0] == 1);
+        assert(input[1] == 2);
+        assert(input[2] == 3);
+        assert(input[3] == 4);
+        assert(input[4] == 5);
+    }
+    return true;
 }
 
 int main(int, char**)
 {
-    test(0);
-    test(1);
-    test(2);
-    test(3);
-    test(10);
-    test(1000);
-
-  return 0;
+    test<int, random_access_iterator<int*> >();
+    test<int, int*>();
+
+#if TEST_STD_VER >= 11
+    test<MoveOnly, random_access_iterator<MoveOnly*>>();
+    test<MoveOnly, MoveOnly*>();
+#endif
+
+#if TEST_STD_VER >= 20
+    static_assert(test<int, random_access_iterator<int*>>());
+    static_assert(test<int, int*>());
+    static_assert(test<MoveOnly, random_access_iterator<MoveOnly*>>());
+    static_assert(test<MoveOnly, MoveOnly*>());
+#endif
+
+    return 0;
 }
diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/sort.heap/sort_heap_comp.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/sort.heap/sort_heap_comp.pass.cpp
--- a/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/sort.heap/sort_heap_comp.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/sort.heap/sort_heap_comp.pass.cpp
@@ -8,69 +8,63 @@
 
 // <algorithm>
 
-// template<RandomAccessIterator Iter, StrictWeakOrder<auto, Iter::value_type> Compare>
-//   requires ShuffleIterator<Iter> && CopyConstructible<Compare>
-//   void
+// template<RandomAccessIterator Iter>
+//   requires ShuffleIterator<Iter> && LessThanComparable<Iter::value_type>
+//   constexpr void  // constexpr in C++20
 //   sort_heap(Iter first, Iter last, Compare comp);
 
 #include <algorithm>
-#include <functional>
-#include <random>
 #include <cassert>
-#include <memory>
 
 #include "test_macros.h"
 #include "test_iterators.h"
 
-struct indirect_less
-{
-    template <class P>
-    bool operator()(const P& x, const P& y)
-        {return *x < *y;}
-};
-
-std::mt19937 randomness;
+#include "test_macros.h"
+#include "test_iterators.h"
+#include "MoveOnly.h"
 
-void test(int N)
+template<class T, class Iter>
+TEST_CONSTEXPR_CXX20 bool test()
 {
-    int* ia = new int [N];
-    for (int i = 0; i < N; ++i)
-        ia[i] = i;
-    std::shuffle(ia, ia+N, randomness);
-    std::make_heap(ia, ia+N, std::greater<int>());
-    std::sort_heap(ia, ia+N, std::greater<int>());
-    assert(std::is_sorted(ia, ia+N, std::greater<int>()));
+    int orig[15] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
+    T work[15] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
+    for (int n = 0; n < 15; ++n) {
+        std::make_heap(work, work+n, std::greater<T>());
+        std::sort_heap(Iter(work), Iter(work+n), std::greater<T>());
+        assert(std::is_sorted(work, work+n, std::greater<T>()));
+        assert(std::is_permutation(work, work+n, orig));
+        std::copy(orig, orig+n, work);
+    }
 
-    typedef random_access_iterator<int *> RI;
-    std::shuffle(RI(ia), RI(ia+N), randomness);
-    std::make_heap(RI(ia), RI(ia+N), std::greater<int>());
-    std::sort_heap(RI(ia), RI(ia+N), std::greater<int>());
-    assert(std::is_sorted(RI(ia), RI(ia+N), std::greater<int>()));
-    delete [] ia;
+    {
+        T input[] = {1, 3, 2, 5, 4};
+        assert(std::is_heap(input, input + 5, std::greater<T>()));
+        std::sort_heap(Iter(input), Iter(input + 5), std::greater<T>());
+        assert(input[0] == 5);
+        assert(input[1] == 4);
+        assert(input[2] == 3);
+        assert(input[3] == 2);
+        assert(input[4] == 1);
+    }
+    return true;
 }
 
 int main(int, char**)
 {
-    test(0);
-    test(1);
-    test(2);
-    test(3);
-    test(10);
-    test(1000);
+    test<int, random_access_iterator<int*> >();
+    test<int, int*>();
 
 #if TEST_STD_VER >= 11
-    {
-    const int N = 1000;
-    std::unique_ptr<int>* ia = new std::unique_ptr<int> [N];
-    for (int i = 0; i < N; ++i)
-        ia[i].reset(new int(i));
-    std::shuffle(ia, ia+N, randomness);
-    std::make_heap(ia, ia+N, indirect_less());
-    std::sort_heap(ia, ia+N, indirect_less());
-    assert(std::is_sorted(ia, ia+N, indirect_less()));
-    delete [] ia;
-    }
+    test<MoveOnly, random_access_iterator<MoveOnly*>>();
+    test<MoveOnly, MoveOnly*>();
+#endif
+
+#if TEST_STD_VER >= 20
+    static_assert(test<int, random_access_iterator<int*>>());
+    static_assert(test<int, int*>());
+    static_assert(test<MoveOnly, random_access_iterator<MoveOnly*>>());
+    static_assert(test<MoveOnly, MoveOnly*>());
 #endif
 
-  return 0;
+    return 0;
 }
diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.sort/partial.sort.copy/partial_sort_copy.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.sort/partial.sort.copy/partial_sort_copy.pass.cpp
--- a/libcxx/test/std/algorithms/alg.sorting/alg.sort/partial.sort.copy/partial_sort_copy.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.sorting/alg.sort/partial.sort.copy/partial_sort_copy.pass.cpp
@@ -13,79 +13,83 @@
 //         && OutputIterator<RAIter, InIter::reference>
 //         && HasLess<InIter::value_type, RAIter::value_type>
 //         && LessThanComparable<RAIter::value_type>
-//   RAIter
+//   constexpr RAIter  // constexpr in C++20
 //   partial_sort_copy(InIter first, InIter last, RAIter result_first, RAIter result_last);
 
 #include <algorithm>
-#include <random>
 #include <cassert>
 
 #include "test_macros.h"
 #include "test_iterators.h"
+#include "MoveOnly.h"
 
-std::mt19937 randomness;
-
-template <class Iter>
-void
-test_larger_sorts(int N, int M)
+template<class T, class Iter, class OutIter>
+TEST_CONSTEXPR_CXX20 bool test()
 {
-    int* input = new int[N];
-    int* output = new int[M];
-    for (int i = 0; i < N; ++i)
-        input[i] = i;
-    std::shuffle(input, input+N, randomness);
-    int* r = std::partial_sort_copy(Iter(input), Iter(input+N), output, output+M);
-    int* e = output + std::min(N, M);
-    assert(r == e);
-    int i = 0;
-    for (int* x = output; x < e; ++x, ++i)
-        assert(*x == i);
-    delete [] output;
-    delete [] input;
-}
+    int orig[15] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
+    T work[15] = {};
+    for (int n = 0; n < 15; ++n) {
+        for (int m = 0; m < 15; ++m) {
+            OutIter it = std::partial_sort_copy(Iter(orig), Iter(orig+n), OutIter(work), OutIter(work+m));
+            if (n <= m) {
+                assert(it == OutIter(work+n));
+                assert(std::is_permutation(OutIter(work), it, orig));
+            } else {
+                assert(it == OutIter(work+m));
+            }
+            assert(std::is_sorted(OutIter(work), it));
+            if (it != OutIter(work)) {
+                // At most m-1 elements in the input are less than the biggest element in the result.
+                int count = 0;
+                for (int i = m; i < n; ++i) {
+                    count += (T(orig[i]) < *(it - 1));
+                }
+                assert(count < m);
+            }
+        }
+    }
 
-template <class Iter>
-void
-test_larger_sorts(int N)
-{
-    test_larger_sorts<Iter>(N, 0);
-    test_larger_sorts<Iter>(N, 1);
-    test_larger_sorts<Iter>(N, 2);
-    test_larger_sorts<Iter>(N, 3);
-    test_larger_sorts<Iter>(N, N/2-1);
-    test_larger_sorts<Iter>(N, N/2);
-    test_larger_sorts<Iter>(N, N/2+1);
-    test_larger_sorts<Iter>(N, N-2);
-    test_larger_sorts<Iter>(N, N-1);
-    test_larger_sorts<Iter>(N, N);
-    test_larger_sorts<Iter>(N, N+1000);
-}
-
-template <class Iter>
-void
-test()
-{
-    test_larger_sorts<Iter>(0, 100);
-    test_larger_sorts<Iter>(10);
-    test_larger_sorts<Iter>(256);
-    test_larger_sorts<Iter>(257);
-    test_larger_sorts<Iter>(499);
-    test_larger_sorts<Iter>(500);
-    test_larger_sorts<Iter>(997);
-    test_larger_sorts<Iter>(1000);
-    test_larger_sorts<Iter>(1009);
+    {
+        int input[] = {3, 4, 2, 5, 1};
+        T output[] = {0, 0, 0};
+        std::partial_sort_copy(Iter(input), Iter(input + 5), OutIter(output), OutIter(output + 3));
+        assert(output[0] == 1);
+        assert(output[1] == 2);
+        assert(output[2] == 3);
+    }
+    return true;
 }
 
 int main(int, char**)
 {
-    int i = 0;
-    std::partial_sort_copy(&i, &i, &i, &i+5);
-    assert(i == 0);
-    test<input_iterator<const int*> >();
-    test<forward_iterator<const int*> >();
-    test<bidirectional_iterator<const int*> >();
-    test<random_access_iterator<const int*> >();
-    test<const int*>();
+    int i = 42;
+    int j = 75;
+    std::partial_sort_copy(&i, &i, &j, &j);  // no-op
+    assert(i == 42);
+    assert(j == 75);
+
+    test<int, random_access_iterator<int*>, random_access_iterator<int*> >();
+    test<int, random_access_iterator<int*>, int*>();
+    test<int, int*, random_access_iterator<int*> >();
+    test<int, int*, int*>();
+
+#if TEST_STD_VER >= 11
+    test<MoveOnly, random_access_iterator<int*>, random_access_iterator<MoveOnly*>>();
+    test<MoveOnly, random_access_iterator<int*>, MoveOnly*>();
+    test<MoveOnly, int*, random_access_iterator<MoveOnly*>>();
+    test<MoveOnly, int*, MoveOnly*>();
+#endif
+
+#if TEST_STD_VER >= 20
+    static_assert(test<int, random_access_iterator<int*>, random_access_iterator<int*>>());
+    static_assert(test<int, int*, random_access_iterator<int*>>());
+    static_assert(test<int, random_access_iterator<int*>, int*>());
+    static_assert(test<int, int*, int*>());
+    static_assert(test<MoveOnly, random_access_iterator<int*>, random_access_iterator<MoveOnly*>>());
+    static_assert(test<MoveOnly, random_access_iterator<int*>, MoveOnly*>());
+    static_assert(test<MoveOnly, int*, random_access_iterator<MoveOnly*>>());
+    static_assert(test<MoveOnly, int*, MoveOnly*>());
+#endif
 
-  return 0;
+    return 0;
 }
diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.sort/partial.sort.copy/partial_sort_copy_comp.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.sort/partial.sort.copy/partial_sort_copy_comp.pass.cpp
--- a/libcxx/test/std/algorithms/alg.sorting/alg.sort/partial.sort.copy/partial_sort_copy_comp.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.sorting/alg.sort/partial.sort.copy/partial_sort_copy_comp.pass.cpp
@@ -14,82 +14,85 @@
 //         && Predicate<Compare, InIter::value_type, RAIter::value_type>
 //         && StrictWeakOrder<Compare, RAIter::value_type>}
 //         && CopyConstructible<Compare>
-//   RAIter
+//   constexpr RAIter  // constexpr in C++20
 //   partial_sort_copy(InIter first, InIter last,
 //                     RAIter result_first, RAIter result_last, Compare comp);
 
 #include <algorithm>
-#include <functional>
-#include <random>
 #include <cassert>
+#include <functional>
 
 #include "test_macros.h"
 #include "test_iterators.h"
+#include "MoveOnly.h"
 
-std::mt19937 randomness;
-
-template <class Iter>
-void
-test_larger_sorts(int N, int M)
+template<class T, class Iter, class OutIter>
+TEST_CONSTEXPR_CXX20 bool test()
 {
-    int* input = new int[N];
-    int* output = new int[M];
-    for (int i = 0; i < N; ++i)
-        input[i] = i;
-    std::shuffle(input, input+N, randomness);
-    int* r = std::partial_sort_copy(Iter(input), Iter(input+N), output, output+M,
-                                    std::greater<int>());
-    int* e = output + std::min(N, M);
-    assert(r == e);
-    int i = 0;
-    for (int* x = output; x < e; ++x, ++i)
-        assert(*x == N-i-1);
-    delete [] output;
-    delete [] input;
-}
+    int orig[15] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
+    T work[15] = {};
+    for (int n = 0; n < 15; ++n) {
+        for (int m = 0; m < 15; ++m) {
+            OutIter it = std::partial_sort_copy(Iter(orig), Iter(orig+n), OutIter(work), OutIter(work+m), std::greater<T>());
+            if (n <= m) {
+                assert(it == OutIter(work+n));
+                assert(std::is_permutation(OutIter(work), it, orig));
+            } else {
+                assert(it == OutIter(work+m));
+            }
+            assert(std::is_sorted(OutIter(work), it, std::greater<T>()));
+            if (it != OutIter(work)) {
+                // At most m-1 elements in the input are greater than the biggest element in the result.
+                int count = 0;
+                for (int i = m; i < n; ++i) {
+                    count += (T(orig[i]) > *(it - 1));
+                }
+                assert(count < m);
+            }
+        }
+    }
 
-template <class Iter>
-void
-test_larger_sorts(int N)
-{
-    test_larger_sorts<Iter>(N, 0);
-    test_larger_sorts<Iter>(N, 1);
-    test_larger_sorts<Iter>(N, 2);
-    test_larger_sorts<Iter>(N, 3);
-    test_larger_sorts<Iter>(N, N/2-1);
-    test_larger_sorts<Iter>(N, N/2);
-    test_larger_sorts<Iter>(N, N/2+1);
-    test_larger_sorts<Iter>(N, N-2);
-    test_larger_sorts<Iter>(N, N-1);
-    test_larger_sorts<Iter>(N, N);
-    test_larger_sorts<Iter>(N, N+1000);
-}
-
-template <class Iter>
-void
-test()
-{
-    test_larger_sorts<Iter>(0, 100);
-    test_larger_sorts<Iter>(10);
-    test_larger_sorts<Iter>(256);
-    test_larger_sorts<Iter>(257);
-    test_larger_sorts<Iter>(499);
-    test_larger_sorts<Iter>(500);
-    test_larger_sorts<Iter>(997);
-    test_larger_sorts<Iter>(1000);
-    test_larger_sorts<Iter>(1009);
+    {
+        int input[] = {3, 4, 2, 5, 1};
+        T output[] = {0, 0, 0};
+        std::partial_sort_copy(Iter(input), Iter(input + 5), OutIter(output), OutIter(output + 3), std::greater<T>());
+        assert(output[0] == 5);
+        assert(output[1] == 4);
+        assert(output[2] == 3);
+    }
+    return true;
 }
 
 int main(int, char**)
 {
-    int i = 0;
-    std::partial_sort_copy(&i, &i, &i, &i+5);
-    assert(i == 0);
-    test<input_iterator<const int*> >();
-    test<forward_iterator<const int*> >();
-    test<bidirectional_iterator<const int*> >();
-    test<random_access_iterator<const int*> >();
-    test<const int*>();
+    int i = 42;
+    int j = 75;
+    std::partial_sort_copy(&i, &i, &j, &j, std::greater<int>());  // no-op
+    assert(i == 42);
+    assert(j == 75);
+
+    test<int, random_access_iterator<int*>, random_access_iterator<int*> >();
+    test<int, random_access_iterator<int*>, int*>();
+    test<int, int*, random_access_iterator<int*> >();
+    test<int, int*, int*>();
+
+#if TEST_STD_VER >= 11
+    test<MoveOnly, random_access_iterator<int*>, random_access_iterator<MoveOnly*>>();
+    test<MoveOnly, random_access_iterator<int*>, MoveOnly*>();
+    test<MoveOnly, int*, random_access_iterator<MoveOnly*>>();
+    test<MoveOnly, int*, MoveOnly*>();
+#endif
+
+#if TEST_STD_VER >= 20
+    static_assert(test<int, random_access_iterator<int*>, random_access_iterator<int*>>());
+    static_assert(test<int, int*, random_access_iterator<int*>>());
+    static_assert(test<int, random_access_iterator<int*>, int*>());
+    static_assert(test<int, int*, int*>());
+    static_assert(test<MoveOnly, random_access_iterator<int*>, random_access_iterator<MoveOnly*>>());
+    static_assert(test<MoveOnly, random_access_iterator<int*>, MoveOnly*>());
+    static_assert(test<MoveOnly, int*, random_access_iterator<MoveOnly*>>());
+    static_assert(test<MoveOnly, int*, MoveOnly*>());
+#endif
 
-  return 0;
+    return 0;
 }
diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.sort/partial.sort/partial_sort.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.sort/partial.sort/partial_sort.pass.cpp
--- a/libcxx/test/std/algorithms/alg.sorting/alg.sort/partial.sort/partial_sort.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.sorting/alg.sort/partial.sort/partial_sort.pass.cpp
@@ -9,65 +9,66 @@
 // <algorithm>
 
 // template<RandomAccessIterator Iter>
-//   requires ShuffleIterator<Iter>
-//         && LessThanComparable<Iter::value_type>
-//   void
+//   requires ShuffleIterator<Iter> && LessThanComparable<Iter::value_type>
+//   constexpr void  // constexpr in C++20
 //   partial_sort(Iter first, Iter middle, Iter last);
 
 #include <algorithm>
-#include <random>
 #include <cassert>
 
 #include "test_macros.h"
+#include "test_iterators.h"
+#include "MoveOnly.h"
 
-std::mt19937 randomness;
-
-void
-test_larger_sorts(int N, int M)
+template<class T, class Iter>
+TEST_CONSTEXPR_CXX20 bool test()
 {
-    assert(N != 0);
-    assert(N >= M);
-    int* array = new int[N];
-    for (int i = 0; i < N; ++i)
-        array[i] = i;
-    std::shuffle(array, array+N, randomness);
-    std::partial_sort(array, array+M, array+N);
-    for (int i = 0; i < M; ++i)
-    {
-        assert(i < N); // quiet analysis warnings
-        assert(array[i] == i);
+    int orig[15] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
+    T work[15] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
+    for (int n = 0; n < 15; ++n) {
+        for (int m = 0; m <= n; ++m) {
+            std::partial_sort(Iter(work), Iter(work+m), Iter(work+n));
+            assert(std::is_sorted(work, work+m));
+            assert(std::is_permutation(work, work+n, orig));
+            // No element in the unsorted portion is less than any element in the sorted portion.
+            for (int i = m; i < n; ++i) {
+                assert(m == 0 || !(work[i] < work[m-1]));
+            }
+            std::copy(orig, orig+15, work);
+        }
     }
-    delete [] array;
-}
 
-void
-test_larger_sorts(int N)
-{
-    test_larger_sorts(N, 0);
-    test_larger_sorts(N, 1);
-    test_larger_sorts(N, 2);
-    test_larger_sorts(N, 3);
-    test_larger_sorts(N, N/2-1);
-    test_larger_sorts(N, N/2);
-    test_larger_sorts(N, N/2+1);
-    test_larger_sorts(N, N-2);
-    test_larger_sorts(N, N-1);
-    test_larger_sorts(N, N);
+    {
+        T input[] = {3, 4, 2, 5, 1};
+        std::partial_sort(Iter(input), Iter(input + 3), Iter(input + 5));
+        assert(input[0] == 1);
+        assert(input[1] == 2);
+        assert(input[2] == 3);
+        assert(input[3] + input[4] == 4 + 5);
+    }
+    return true;
 }
 
 int main(int, char**)
 {
-    int i = 0;
-    std::partial_sort(&i, &i, &i);
-    assert(i == 0);
-    test_larger_sorts(10);
-    test_larger_sorts(256);
-    test_larger_sorts(257);
-    test_larger_sorts(499);
-    test_larger_sorts(500);
-    test_larger_sorts(997);
-    test_larger_sorts(1000);
-    test_larger_sorts(1009);
+    int i = 42;
+    std::partial_sort(&i, &i, &i);  // no-op
+    assert(i == 42);
+
+    test<int, random_access_iterator<int*> >();
+    test<int, int*>();
+
+#if TEST_STD_VER >= 11
+    test<MoveOnly, random_access_iterator<MoveOnly*>>();
+    test<MoveOnly, MoveOnly*>();
+#endif
+
+#if TEST_STD_VER >= 20
+    static_assert(test<int, random_access_iterator<int*>>());
+    static_assert(test<int, int*>());
+    static_assert(test<MoveOnly, random_access_iterator<MoveOnly*>>());
+    static_assert(test<MoveOnly, MoveOnly*>());
+#endif
 
-  return 0;
+    return 0;
 }
diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.sort/partial.sort/partial_sort_comp.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.sort/partial.sort/partial_sort_comp.pass.cpp
--- a/libcxx/test/std/algorithms/alg.sorting/alg.sort/partial.sort/partial_sort_comp.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.sorting/alg.sort/partial.sort/partial_sort_comp.pass.cpp
@@ -11,87 +11,66 @@
 // template<RandomAccessIterator Iter, StrictWeakOrder<auto, Iter::value_type> Compare>
 //   requires ShuffleIterator<Iter>
 //         && CopyConstructible<Compare>
-//   void
+//   constexpr void  // constexpr in C++20
 //   partial_sort(Iter first, Iter middle, Iter last, Compare comp);
 
 #include <algorithm>
-#include <vector>
-#include <functional>
-#include <random>
 #include <cassert>
-#include <cstddef>
-#include <memory>
+#include <functional>
 
 #include "test_macros.h"
+#include "test_iterators.h"
+#include "MoveOnly.h"
 
-struct indirect_less
+template<class T, class Iter>
+TEST_CONSTEXPR_CXX20 bool test()
 {
-    template <class P>
-    bool operator()(const P& x, const P& y)
-        {return *x < *y;}
-};
-
-std::mt19937 randomness;
+    int orig[15] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
+    T work[15] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
+    for (int n = 0; n < 15; ++n) {
+        for (int m = 0; m <= n; ++m) {
+            std::partial_sort(Iter(work), Iter(work+m), Iter(work+n), std::greater<T>());
+            assert(std::is_sorted(work, work+m, std::greater<T>()));
+            assert(std::is_permutation(work, work+n, orig));
+            // No element in the unsorted portion is greater than any element in the sorted portion.
+            for (int i = m; i < n; ++i) {
+                assert(m == 0 || !(work[i] > work[m-1]));
+            }
+            std::copy(orig, orig+15, work);
+        }
+    }
 
-void
-test_larger_sorts(int N, int M)
-{
-    assert(N != 0);
-    assert(N >= M);
-    int* array = new int[N];
-    for (int i = 0; i < N; ++i)
-        array[i] = i;
-    std::shuffle(array, array+N, randomness);
-    std::partial_sort(array, array+M, array+N, std::greater<int>());
-    for (int i = 0; i < M; ++i)
     {
-        assert(i < N); // quiet analysis warnings
-        assert(array[i] == N-i-1);
+        T input[] = {3, 4, 2, 5, 1};
+        std::partial_sort(Iter(input), Iter(input + 3), Iter(input + 5), std::greater<T>());
+        assert(input[0] == 5);
+        assert(input[1] == 4);
+        assert(input[2] == 3);
+        assert(input[3] + input[4] == 1 + 2);
     }
-    delete [] array;
-}
-
-void
-test_larger_sorts(int N)
-{
-    test_larger_sorts(N, 0);
-    test_larger_sorts(N, 1);
-    test_larger_sorts(N, 2);
-    test_larger_sorts(N, 3);
-    test_larger_sorts(N, N/2-1);
-    test_larger_sorts(N, N/2);
-    test_larger_sorts(N, N/2+1);
-    test_larger_sorts(N, N-2);
-    test_larger_sorts(N, N-1);
-    test_larger_sorts(N, N);
+    return true;
 }
 
 int main(int, char**)
 {
-    {
-    int i = 0;
-    std::partial_sort(&i, &i, &i);
-    assert(i == 0);
-    test_larger_sorts(10);
-    test_larger_sorts(256);
-    test_larger_sorts(257);
-    test_larger_sorts(499);
-    test_larger_sorts(500);
-    test_larger_sorts(997);
-    test_larger_sorts(1000);
-    test_larger_sorts(1009);
-    }
+    int i = 42;
+    std::partial_sort(&i, &i, &i, std::greater<int>());  // no-op
+    assert(i == 42);
+
+    test<int, random_access_iterator<int*> >();
+    test<int, int*>();
 
 #if TEST_STD_VER >= 11
-    {
-    std::vector<std::unique_ptr<int> > v(1000);
-    for (int i = 0; static_cast<std::size_t>(i) < v.size(); ++i)
-        v[i].reset(new int(i));
-    std::partial_sort(v.begin(), v.begin() + v.size()/2, v.end(), indirect_less());
-    for (int i = 0; static_cast<std::size_t>(i) < v.size()/2; ++i)
-        assert(*v[i] == i);
-    }
+    test<MoveOnly, random_access_iterator<MoveOnly*>>();
+    test<MoveOnly, MoveOnly*>();
+#endif
+
+#if TEST_STD_VER >= 20
+    static_assert(test<int, random_access_iterator<int*>>());
+    static_assert(test<int, int*>());
+    static_assert(test<MoveOnly, random_access_iterator<MoveOnly*>>());
+    static_assert(test<MoveOnly, MoveOnly*>());
 #endif
 
-  return 0;
+    return 0;
 }
diff --git a/libcxx/test/support/MoveOnly.h b/libcxx/test/support/MoveOnly.h
--- a/libcxx/test/support/MoveOnly.h
+++ b/libcxx/test/support/MoveOnly.h
@@ -32,7 +32,11 @@
     constexpr int get() const {return data_;}
 
     constexpr bool operator==(const MoveOnly& x) const {return data_ == x.data_;}
+    constexpr bool operator!=(const MoveOnly& x) const {return data_ != x.data_;}
     constexpr bool operator< (const MoveOnly& x) const {return data_ <  x.data_;}
+    constexpr bool operator<=(const MoveOnly& x) const {return data_ <= x.data_;}
+    constexpr bool operator> (const MoveOnly& x) const {return data_ >  x.data_;}
+    constexpr bool operator>=(const MoveOnly& x) const {return data_ >= x.data_;}
     TEST_CONSTEXPR_CXX14 MoveOnly operator+(const MoveOnly& x) const
         { return MoveOnly{data_ + x.data_}; }
     TEST_CONSTEXPR_CXX14 MoveOnly operator*(const MoveOnly& x) const