diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt
--- a/libcxx/include/CMakeLists.txt
+++ b/libcxx/include/CMakeLists.txt
@@ -216,6 +216,7 @@
   __coroutine/noop_coroutine_handle.h
   __coroutine/trivial_awaitables.h
   __debug
+  __debug_utils/randomize_range.h
   __errc
   __filesystem/copy_options.h
   __filesystem/directory_entry.h
diff --git a/libcxx/include/__algorithm/nth_element.h b/libcxx/include/__algorithm/nth_element.h
--- a/libcxx/include/__algorithm/nth_element.h
+++ b/libcxx/include/__algorithm/nth_element.h
@@ -14,13 +14,10 @@
 #include <__algorithm/sort.h>
 #include <__config>
 #include <__debug>
+#include <__debug_utils/randomize_range.h>
 #include <__iterator/iterator_traits.h>
 #include <__utility/swap.h>
 
-#if defined(_LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY)
-#  include <__algorithm/shuffle.h>
-#endif
-
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
@@ -227,12 +224,12 @@
 void
 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
 {
-  _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __last);
+  std::__debug_randomize_range(__first, __last);
   typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
   _VSTD::__nth_element<_Comp_ref>(__first, __nth, __last, __comp);
-  _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __nth);
+  std::__debug_randomize_range(__first, __nth);
   if (__nth != __last) {
-    _LIBCPP_DEBUG_RANDOMIZE_RANGE(++__nth, __last);
+    std::__debug_randomize_range(++__nth, __last);
   }
 }
 
diff --git a/libcxx/include/__algorithm/partial_sort.h b/libcxx/include/__algorithm/partial_sort.h
--- a/libcxx/include/__algorithm/partial_sort.h
+++ b/libcxx/include/__algorithm/partial_sort.h
@@ -16,13 +16,10 @@
 #include <__algorithm/sort_heap.h>
 #include <__config>
 #include <__debug>
+#include <__debug_utils/randomize_range.h>
 #include <__iterator/iterator_traits.h>
 #include <__utility/swap.h>
 
-#if defined(_LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY)
-#  include <__algorithm/shuffle.h>
-#endif
-
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
@@ -55,10 +52,10 @@
 partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
              _Compare __comp)
 {
-  _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __last);
+  std::__debug_randomize_range(__first, __last);
   typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
   _VSTD::__partial_sort<_Comp_ref>(__first, __middle, __last, __comp);
-  _LIBCPP_DEBUG_RANDOMIZE_RANGE(__middle, __last);
+  std::__debug_randomize_range(__middle, __last);
 }
 
 template <class _RandomAccessIterator>
diff --git a/libcxx/include/__algorithm/sort.h b/libcxx/include/__algorithm/sort.h
--- a/libcxx/include/__algorithm/sort.h
+++ b/libcxx/include/__algorithm/sort.h
@@ -17,6 +17,7 @@
 #include <__bits>
 #include <__config>
 #include <__debug>
+#include <__debug_utils/randomize_range.h>
 #include <__functional/operations.h>
 #include <__functional/ranges_operations.h>
 #include <__iterator/iterator_traits.h>
@@ -24,10 +25,6 @@
 #include <climits>
 #include <memory>
 
-#if defined(_LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY)
-#  include <__algorithm/shuffle.h>
-#endif
-
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
@@ -582,7 +579,7 @@
 template <class _RandomAccessIterator, class _Comp>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
 void __sort_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp& __comp) {
-  _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __last);
+  std::__debug_randomize_range(__first, __last);
   using _Comp_ref = typename __comp_ref_type<_Comp>::type;
   if (__libcpp_is_constant_evaluated()) {
     std::__partial_sort<_Comp_ref>(__first, __last, __last, _Comp_ref(__comp));
diff --git a/libcxx/include/__debug b/libcxx/include/__debug
--- a/libcxx/include/__debug
+++ b/libcxx/include/__debug
@@ -28,22 +28,6 @@
 # define _LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY
 #endif
 
-// TODO: Define this as a function instead
-#if defined(_LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY)
-# if defined(_LIBCPP_CXX03_LANG)
-#   error Support for unspecified stability is only for C++11 and higher
-# endif
-# define _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __last)                                                         \
-    do {                                                                                                        \
-      if (!__builtin_is_constant_evaluated())                                                                   \
-        std::shuffle(__first, __last, __libcpp_debug_randomizer());                                             \
-    } while (false)
-#else
-# define _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __last)                                                         \
-    do {                                                                                                        \
-    } while (false)
-#endif
-
 #ifdef _LIBCPP_ENABLE_DEBUG_MODE
 #   define _LIBCPP_DEBUG_ASSERT(x, m) _LIBCPP_ASSERT(::std::__libcpp_is_constant_evaluated() || (x), m)
 #else
diff --git a/libcxx/include/__debug_utils/randomize_range.h b/libcxx/include/__debug_utils/randomize_range.h
new file mode 100644
--- /dev/null
+++ b/libcxx/include/__debug_utils/randomize_range.h
@@ -0,0 +1,42 @@
+//===----------------------------------------------------------------------===//
+//
+// 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___LIBCXX_DEBUG_RANDOMIZE_RANGE_H
+#define _LIBCPP___LIBCXX_DEBUG_RANDOMIZE_RANGE_H
+
+#include <__config>
+
+#ifdef _LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY
+#  include <__algorithm/shuffle.h>
+#  include <__type_traits/is_constant_evaluated.h>
+#endif
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template <class _Iterator>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 void __debug_randomize_range(_Iterator __first, _Iterator __last) {
+#ifdef _LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY
+#  ifdef _LIBCPP_CXX03_LANG
+#    error Support for unspecified stability is only for C++11 and higher
+#  endif
+
+  if (!__libcpp_is_constant_evaluated())
+    std::shuffle(__first, __last, __libcpp_debug_randomizer());
+#else
+  (void)__first;
+  (void)__last;
+#endif
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP___LIBCXX_DEBUG_RANDOMIZE_RANGE_H
diff --git a/libcxx/include/module.modulemap.in b/libcxx/include/module.modulemap.in
--- a/libcxx/include/module.modulemap.in
+++ b/libcxx/include/module.modulemap.in
@@ -747,6 +747,11 @@
     header "latch"
     export *
   }
+
+  module __debug_utils {
+    module randomize_range { private header "__debug_utils/randomize_range.h" }
+  }
+
   module limits {
     header "limits"
     export *
diff --git a/libcxx/test/libcxx/private_headers.verify.cpp b/libcxx/test/libcxx/private_headers.verify.cpp
--- a/libcxx/test/libcxx/private_headers.verify.cpp
+++ b/libcxx/test/libcxx/private_headers.verify.cpp
@@ -248,6 +248,7 @@
 #include <__coroutine/coroutine_traits.h> // expected-error@*:* {{use of private header from outside its module: '__coroutine/coroutine_traits.h'}}
 #include <__coroutine/noop_coroutine_handle.h> // expected-error@*:* {{use of private header from outside its module: '__coroutine/noop_coroutine_handle.h'}}
 #include <__coroutine/trivial_awaitables.h> // expected-error@*:* {{use of private header from outside its module: '__coroutine/trivial_awaitables.h'}}
+#include <__debug_utils/randomize_range.h> // expected-error@*:* {{use of private header from outside its module: '__debug_utils/randomize_range.h'}}
 #include <__errc> // expected-error@*:* {{use of private header from outside its module: '__errc'}}
 #include <__filesystem/copy_options.h> // expected-error@*:* {{use of private header from outside its module: '__filesystem/copy_options.h'}}
 #include <__filesystem/directory_entry.h> // expected-error@*:* {{use of private header from outside its module: '__filesystem/directory_entry.h'}}