diff --git a/libcxx/docs/ReleaseNotes.rst b/libcxx/docs/ReleaseNotes.rst
--- a/libcxx/docs/ReleaseNotes.rst
+++ b/libcxx/docs/ReleaseNotes.rst
@@ -39,8 +39,13 @@
 ------------
 
  - Implemented P0627R6 (Function to mark unreachable code)
+
  - Implemented P1165R1 (Make stateful allocator propagation more consistent for ``operator+(basic_string)``)
 
+ - `pop_heap` now uses an algorithm known as "bottom-up heapsort" or
+   "heapsort with bounce" to reduce the number of comparisons, and rearranges
+   elements using move-assignment instead of `swap`.
+
 API Changes
 -----------
 
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/sort.heap/complexity.pass.cpp b/libcxx/test/libcxx/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/libcxx/algorithms/alg.sorting/alg.heap.operations/sort.heap/complexity.pass.cpp
@@ -64,9 +64,9 @@
   stats = {};
   std::sort_heap(v.begin(), v.end());
   assert(stats.copied == 0);
-  assert(stats.moved == 1'900'731);
+  assert(stats.moved == 1'764'997);
 #ifndef _LIBCPP_DEBUG
-  assert(stats.compared == 2'831'757);
+  assert(stats.compared == 1'534'701);
 #endif
 
   assert(std::is_sorted(v.begin(), v.end()));