diff options
| author | Arthur O'Dwyer <arthur.j.odwyer@gmail.com> | 2021-12-29 14:11:46 -0500 |
|---|---|---|
| committer | Arthur O'Dwyer <arthur.j.odwyer@gmail.com> | 2022-03-08 13:48:21 -0500 |
| commit | 79d08e398c17e83b118b837ab0b52107fd294c3e (patch) | |
| tree | 5df7c0a35dd5a6c1baca3f9aac90136c3b30f5eb /flang/lib/Frontend/CompilerInvocation.cpp | |
| parent | e3d3755c4745aee33b55ad4e5ab72c46e4133a8e (diff) | |
| download | llvm-79d08e398c17e83b118b837ab0b52107fd294c3e.zip llvm-79d08e398c17e83b118b837ab0b52107fd294c3e.tar.gz llvm-79d08e398c17e83b118b837ab0b52107fd294c3e.tar.bz2 | |
[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
Diffstat (limited to 'flang/lib/Frontend/CompilerInvocation.cpp')
0 files changed, 0 insertions, 0 deletions