4 ms·
Any particular reason none of the implementations just do a random pick of a pivot? This usually is good enough to prevent the O(n^2) solution that the diet imp
by kylepdm 10y ago
Any particular reason none of the implementations just do a random pick of a pivot? This usually is good enough to prevent the O(n^2) solution that the diet implementation runs into.
- xyzzyz 10y agoThe sort in standard library should have predictable performance, so "usually" is not good enough. Moreover, to do random pivot, you need to have a good source of randomness, and if you don't, an attacker often could predict the sequence of pivot choices, and prepare the input to ensure "random" choice of pivot results in a quadratic performance.
- CJefferson 10y agoI experimented with this for std::sort in g++. It turns out it's really annoying when your sort function produces different output on different runs. While quick sort doesn't guarantee the ordering of equal elements, you at least want it to be the same each time you run a particular compile of your program.