[libc++] "Bottom-up heapsort" improvement to sort_heap.
https://en.wikipedia.org/wiki/Heapsort#Bottom-up_heapsort
In `pop_heap` specifically, the item we insert at the top and
sift downward is guaranteed to be leaf-sized, so we expect it
to go pretty far down. Sift it down as if it were INT_MIN, and
then bubble it back up if needed.
Also known as "heapsort with bounce."
Numbers are here: https://godbolt.org/z/cvfnYW6fe
Fixes #10008.
Differential Revision: https://reviews.llvm.org/D118003
NOKEYCHECK=True
GitOrigin-RevId: 79d08e398c17e83b118b837ab0b52107fd294c3e
diff --git a/docs/ReleaseNotes.rst b/docs/ReleaseNotes.rst
index ea7235e..d78549e 100644
--- a/docs/ReleaseNotes.rst
+++ b/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
-----------