20-Apr-2013 16:22, Chris Cain пишет:
On Friday, 19 April 2013 at 22:56:00 UTC, bearophile wrote:
So, why isn't TimSort the default?
Probably because someone thinks that "on average" the other sort is
faster.
In theory the other should be faster, because if you relax the
constraints of the sort being stable I think in theory you should be
able to write a little faster sorting algorithm (I don't know if this
is true).
I'm just throwing my 2c in, but I think TimSort ought to be the default.
It's simply the safer option. Since worst-case performance can be
designed (and it can be designed unless the pivots are, at least,
pseudo-randomly chosen), there is a very real risk of the default sort
being used in a way that can be compromised by an attacker. From this
perspective, seems to be like TimSort being default would support the
design goal #5 of D, "Make doing things the right way easier than the
wrong way."
And this all is good but TimSort allocates O(N) memory. The constant in
front of N is smallish less then 1.0 but it could cause some grief.
--
Dmitry Olshansky
