diff --git a/libcxx/include/__algorithm/pop_heap.h b/libcxx/include/__algorithm/pop_heap.h
--- a/libcxx/include/__algorithm/pop_heap.h
+++ b/libcxx/include/__algorithm/pop_heap.h
@@ -11,10 +11,11 @@
 
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
+#include <__algorithm/push_heap.h>
 #include <__algorithm/sift_down.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
-#include <__utility/swap.h>
+#include <__utility/move.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
@@ -28,10 +29,21 @@
 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
            typename iterator_traits<_RandomAccessIterator>::difference_type __len)
 {
+    using value_type = typename iterator_traits<_RandomAccessIterator>::value_type;
+
     if (__len > 1)
     {
-        swap(*__first, *--__last);
-        _VSTD::__sift_down<_Compare>(__first, __comp, __len - 1, __first);
+        value_type __top = std::move(*__first);  // create a hole at __first
+        _RandomAccessIterator __hole = std::__floyd_sift_down<_Compare>(__first, __comp, __len);
+        --__last;
+        if (__hole == __last) {
+            *__hole = std::move(__top);
+        } else {
+            *__hole = std::move(*__last);
+            ++__hole;
+            *__last = std::move(__top);
+            std::__sift_up<_Compare>(__first, __hole, __comp, __hole - __first);
+        }
     }
 }
 
diff --git a/libcxx/include/__algorithm/sift_down.h b/libcxx/include/__algorithm/sift_down.h
--- a/libcxx/include/__algorithm/sift_down.h
+++ b/libcxx/include/__algorithm/sift_down.h
@@ -9,6 +9,7 @@
 #ifndef _LIBCPP___ALGORITHM_SIFT_DOWN_H
 #define _LIBCPP___ALGORITHM_SIFT_DOWN_H
 
+#include <__assert>
 #include <__config>
 #include <__iterator/iterator_traits.h>
 #include <__utility/move.h>
@@ -73,6 +74,38 @@
     *__start = _VSTD::move(__top);
 }
 
+template <class _Compare, class _RandomAccessIterator>
+_LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator
+__floyd_sift_down(_RandomAccessIterator __first, _Compare __comp,
+                  typename iterator_traits<_RandomAccessIterator>::difference_type __len)
+{
+    using difference_type = typename iterator_traits<_RandomAccessIterator>::difference_type;
+    _LIBCPP_ASSERT(__len >= 2, "shouldn't be called unless __len >= 2");
+
+    _RandomAccessIterator __hole = __first;
+    _RandomAccessIterator __child_i = __first;
+    difference_type __child = 0;
+
+    while (true) {
+        __child_i += difference_type(__child + 1);
+        __child = 2 * __child + 1;
+
+        if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + difference_type(1)))) {
+            // right-child exists and is greater than left-child
+            ++__child_i;
+            ++__child;
+        }
+
+        // swap __hole with its largest child
+        *__hole = std::move(*__child_i);
+        __hole = std::move(__child_i);
+
+        // if __hole is now a leaf, we're done
+        if (__child > (__len - 2) / 2)
+            return __hole;
+    }
+}
+
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_SIFT_DOWN_H
diff --git a/libcxx/test/libcxx/algorithms/alg.sorting/alg.heap.operations/make.heap/complexity.pass.cpp b/libcxx/test/libcxx/algorithms/alg.sorting/alg.heap.operations/make.heap/complexity.pass.cpp
new file mode 100644
--- /dev/null
+++ b/libcxx/test/libcxx/algorithms/alg.sorting/alg.heap.operations/make.heap/complexity.pass.cpp
@@ -0,0 +1,73 @@
+//===----------------------------------------------------------------------===//
+//
+// 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
+
+// <algorithm>
+
+// template<RandomAccessIterator Iter>
+//   constexpr void  // constexpr in C++20
+//     sort_heap(Iter first, Iter last);
+
+#include <algorithm>
+#include <cassert>
+#include <random>
+
+#include "test_macros.h"
+
+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;
+  }
+  friend bool operator<(const MyInt& a, const MyInt& b) {
+    ++stats.compared;
+    return a.value < b.value;
+  }
+};
+
+int main(int, char**)
+{
+  const int N = 100'000;
+  std::vector<MyInt> v;
+  v.reserve(N);
+  std::mt19937 g;
+  for (int i = 0; i < N; ++i)
+    v.emplace_back(g());
+
+  // 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::make_heap(v.begin(), v.end());
+  assert(stats.copied == 0);
+  assert(stats.moved == 153'486);
+  assert(stats.compared == 188'285);
+
+  assert(std::is_heap(v.begin(), v.end()));
+
+  return 0;
+}
diff --git a/libcxx/test/libcxx/algorithms/alg.sorting/alg.heap.operations/sort.heap/complexity.pass.cpp b/libcxx/test/libcxx/algorithms/alg.sorting/alg.heap.operations/sort.heap/complexity.pass.cpp
new file mode 100644
--- /dev/null
+++ b/libcxx/test/libcxx/algorithms/alg.sorting/alg.heap.operations/sort.heap/complexity.pass.cpp
@@ -0,0 +1,74 @@
+//===----------------------------------------------------------------------===//
+//
+// 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
+
+// <algorithm>
+
+// template<RandomAccessIterator Iter>
+//   constexpr void  // constexpr in C++20
+//     sort_heap(Iter first, Iter last);
+
+#include <algorithm>
+#include <cassert>
+#include <random>
+
+#include "test_macros.h"
+
+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;
+  }
+  friend bool operator<(const MyInt& a, const MyInt& b) {
+    ++stats.compared;
+    return a.value < b.value;
+  }
+};
+
+int main(int, char**)
+{
+  const int N = 100'000;
+  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);
+  assert(stats.compared == 1'534'701);
+
+  assert(std::is_sorted(v.begin(), v.end()));
+
+  return 0;
+}