There was a recent post by Voultapher from the sort-research-rs project on Branchless Lomuto Partitioning<p><a href="https://github.com/Voultapher/sort-research-rs/blob/main/writeup/lomcyc_partition/text.md">https://github.com/Voultapher/sort-research-rs/blob/main/wri...</a><p>Discussion here:<p><a href="https://news.ycombinator.com/item?id=38528452">https://news.ycombinator.com/item?id=38528452</a><p>This post by orlp (creator of Pattern-defeating Quicksort and Glidesort) was linked to in the above post, and I found both to be interesting.
What can you actually sort branch-free? Doesn't the comparison have to be inlined, and tiny, not to mention itself branchless? Forget string keys.<p>IPv4 addresses in a routing table or something.<p>Pointers, by increasing or decreasing address. Useful if we want to compact the objects in memory.<p>It's useful to sort floating-point values in a certain way before adding them together, to avoid adding a low magnitude X to a big magnitude Y such that X disappears.
Lomuto partitioning is flawed though; when implementing Quicksort, you want the original Hoare one.<p>Has someone attempted branchless Hoare partitioning?