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.
The 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.
I 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.
xyzzyz|9 years ago
CJefferson|9 years ago
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.