Okay, with scandum's prodding I've looked into this more deeply and need to add much more context. Firstly, I was very much wrong and apologies are in order. Wh

Okay, with scandum's prodding I've looked into this more deeply and need to add much more context. Firstly, I was very much wrong and apologies are in order. What I wrote was based on the assumption that Fluxsort trades speed for stability. It doesn't, apparently: the partitioning seems to be faster and also stable. Possibly more so than the benchmarks show. It's a crude measure, but I ran perf top during benchmarks, and pdqsort spent significantly more time in its partition than Flux did in its own. So the only real drawback is O(n) rather than O(log(n)) memory usage. Memory's cheap, although I guess some users will decide this isn't acceptable. A fast partition that happens to be stable is great to have. The in-place scheme used by pdqsort has one advantage, which that it naturally puts reverse-sorted data in order. Other than that it tends to mangle everything. Stable partitioning doesn't do this, and might even be able to draw out order from interleaved sequences that a merge sort (or insertion sort) could later take advantage of. BlockQuicksort uses a fast index generation method to produce indices for elements that are then swapped. Fluxsort skips all this and moves an element to both possible positions immediately; it then uses the comparison result to increment one partition index allowing the other position to be overwritten. It's the simpler organization of stable partitioning that allows this to be fast. There's also some cleverness in not immediately moving the second partition to put it after the first, but instead partitioning it from where it sits. I've looked into stable partitioning, and I know branchless algorithms well enough that I could have written this. But I didn't!