diff --git a/libcxx/docs/Status/Cxx20Issues.csv b/libcxx/docs/Status/Cxx20Issues.csv
--- a/libcxx/docs/Status/Cxx20Issues.csv
+++ b/libcxx/docs/Status/Cxx20Issues.csv
@@ -1,6 +1,6 @@
 "Issue #","Issue Name","Meeting","Status","First released version","Labels"
 "`2070 <https://wg21.link/LWG2070>`__","``allocate_shared``\  should use ``allocator_traits<A>::construct``\ ","Toronto","Resolved by `P0674R1 <https://wg21.link/P0674R1>`__",""
-"`2444 <https://wg21.link/LWG2444>`__","Inconsistent complexity for ``std::sort_heap``\ ","Toronto","",""
+"`2444 <https://wg21.link/LWG2444>`__","Inconsistent complexity for ``std::sort_heap``\ ","Toronto","|Nothing To Do|",""
 "`2593 <https://wg21.link/LWG2593>`__","Moved-from state of Allocators","Toronto","",""
 "`2597 <https://wg21.link/LWG2597>`__","``std::log``\  misspecified for complex numbers","Toronto","",""
 "`2783 <https://wg21.link/LWG2783>`__","``stack::emplace()``\  and ``queue::emplace()``\  should return ``decltype(auto)``\ ","Toronto","|Complete|",""
diff --git a/libcxx/test/libcxx/algorithms/alg.sorting/alg.heap.operations/sort.heap/complexity.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/sort.heap/complexity.pass.cpp
rename from libcxx/test/libcxx/algorithms/alg.sorting/alg.heap.operations/sort.heap/complexity.pass.cpp
rename to libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/sort.heap/complexity.pass.cpp
--- a/libcxx/test/libcxx/algorithms/alg.sorting/alg.heap.operations/sort.heap/complexity.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/sort.heap/complexity.pass.cpp
@@ -21,8 +21,8 @@
 
 struct Stats {
   int compared = 0;
-  int copied = 0;
-  int moved = 0;
+  int copied   = 0;
+  int moved    = 0;
 } stats;
 
 struct MyInt {
@@ -46,30 +46,30 @@
   }
 };
 
-int main(int, char**)
-{
-  const int N = 100'000;
+int main(int, char**) {
+  constexpr int N = (1 << 20);
   std::vector<MyInt> v;
   v.reserve(N);
   std::mt19937 g;
-  for (int i = 0; i < N; ++i)
-    v.emplace_back(g());
-  std::make_heap(v.begin(), v.end());
-
-  // The exact stats of our current implementation are recorded here.
-  // If something changes to make them go a bit up or down, that's probably fine,
-  // and we can just update this test.
-  // But if they suddenly leap upward, that's a bad thing.
-
-  stats = {};
-  std::sort_heap(v.begin(), v.end());
-  assert(stats.copied == 0);
-  assert(stats.moved == 1'764'997);
+  for (int i = 0; i < N; ++i) {
+    v.emplace_back(i);
+  }
+  for (int logn = 10; logn <= 20; ++logn) {
+    const int n = (1 << logn);
+    auto first  = v.begin();
+    auto last   = v.begin() + n;
+    std::shuffle(first, last, g);
+    std::make_heap(first, last);
+    // The exact stats of our current implementation are recorded here.
+    stats = {};
+    std::sort_heap(first, last);
+    LIBCPP_ASSERT(stats.copied == 0);
+    LIBCPP_ASSERT(stats.moved <= 2 * n + n * logn);
 #ifndef _LIBCPP_ENABLE_DEBUG_MODE
-  assert(stats.compared == 1'534'701);
+    LIBCPP_ASSERT(stats.compared <= n * logn);
 #endif
-
-  assert(std::is_sorted(v.begin(), v.end()));
-
+    LIBCPP_ASSERT(std::is_sorted(first, last));
+    LIBCPP_ASSERT(stats.compared <= 2 * n * logn);
+  }
   return 0;
 }
diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/sort.heap/ranges_sort_heap.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/sort.heap/ranges_sort_heap.pass.cpp
--- a/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/sort.heap/ranges_sort_heap.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/sort.heap/ranges_sort_heap.pass.cpp
@@ -25,6 +25,7 @@
 #include <array>
 #include <concepts>
 #include <functional>
+#include <random>
 #include <ranges>
 
 #include "almost_satisfies_types.h"
@@ -212,9 +213,63 @@
   return true;
 }
 
+struct Stats {
+  int compared = 0;
+  int copied   = 0;
+  int moved    = 0;
+} stats;
+
+struct MyInt {
+  int value;
+  explicit MyInt(int xval) : value(xval) {}
+  MyInt(const MyInt& other) : value(other.value) { ++stats.copied; }
+  MyInt(MyInt&& other) : value(other.value) { ++stats.moved; }
+  MyInt& operator=(const MyInt& other) {
+    value = other.value;
+    ++stats.copied;
+    return *this;
+  }
+  MyInt& operator=(MyInt&& other) {
+    value = other.value;
+    ++stats.moved;
+    return *this;
+  }
+  static bool Comp(const MyInt& a, const MyInt& b) {
+    ++stats.compared;
+    return a.value < b.value;
+  }
+};
+
+void test_complexity() {
+  constexpr int N = (1 << 20);
+  std::vector<MyInt> v;
+  v.reserve(N);
+  std::mt19937 g;
+  for (int i = 0; i < N; ++i) {
+    v.emplace_back(i);
+  }
+  for (int logn = 10; logn <= 20; ++logn) {
+    const int n = (1 << logn);
+    auto first  = v.begin();
+    auto last   = v.begin() + n;
+    std::shuffle(first, last, g);
+    std::make_heap(first, last, &MyInt::Comp);
+    // The exact stats of our current implementation are recorded here.
+    stats = {};
+    std::ranges::sort_heap(first, last, &MyInt::Comp);
+    LIBCPP_ASSERT(stats.copied == 0);
+    LIBCPP_ASSERT(stats.moved <= 2 * n + n * logn);
+#ifndef _LIBCPP_ENABLE_DEBUG_MODE
+    LIBCPP_ASSERT(stats.compared <= n * logn);
+#endif
+    LIBCPP_ASSERT(std::is_sorted(first, last, &MyInt::Comp));
+    LIBCPP_ASSERT(stats.compared <= 2 * n * logn);
+  }
+}
+
 int main(int, char**) {
   test();
   static_assert(test());
-
+  test_complexity();
   return 0;
 }