> Doesn't the comparison have to be inlined, and tiny, not to mention itself branchless?
Yes.
This generally means floats and integers, or small combinations thereof. Note that this is after projection of the comparison operator, so things can remain branchless when sorting e.g. strings by length.
The inlining generally isn't an issue in languages like C++ and Rust.
> Forget string keys.
You can sort string keys (mostly) branchlessly with radix sorting, but yes for comparison sorting you can forget it.
Re:Branchless Lomuto Partitioning
by anonymoushn on Wednesday December 06, 2023 @10:52PM
(#38552640)
For string keys, I think you could do multi-key quicksort with almost no branches, but the partitioning becomes more troublesome because you need to separate elements that are <, =, and > your pivot.
IPv4 addresses in a routing table or something.
Pointers, by increasing or decreasing address. Useful if we want to compact the objects in memory.
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.