Quadratic time to sort in a simple case?

[Dmitry Olshansky]

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