On 01/20/2016 10:20 AM, Andrei Alexandrescu wrote: [snip]
And btw I now understand better why medianOfMedians is not so fast in practice. In fact my wishy-washy version at https://github.com/andralex/phobos/commit/9e004c35b824aac108e0e615183065e73384e9f9 seems to be practically attractive for choosing a good pivot even though it doesn't offer theoretical guarantees. I wonder how some jitter can be injected into it so as to improve its worst-case performance.
Andrei