Worst-case performance of quickSort / getPivot

[Chris Cain]

On Saturday, 16 November 2013 at 23:40:39 UTC, Andrei 
Alexandrescu wrote:
>
> This is in response to what? Are you trying to talk me out of 
> the pigeonhole principle?
>...
> I understand and appreciate that Timsort is a nicely optimized 
> algorithm. This has nothing to do with it doing more work than 
> an unstable sort that is just as nicely optimized.
>
> At the end of the day whatever stable sorting algorithms are 
> out there, their set is included in the set of all sorting 
> algorithms. In order to preserve stability, stable sorting 
> algorithms need to do nonnegative extra work.
>
>
> Andrei

I think it's more complicated than that. Let's assume for a 
moment that you've proven that such an unstable sort must exist 
that is faster (I'm not convinced that it necessarily must take 
extra work to maintain stability). You have not shown how much 
faster it might be (it could be only 1% faster) nor how much work 
it would take to discover (even an ideal pivot choice for 
quicksort actually cannot be as fast as Timsort on an already 
sorted sequence, and quicksort is not an appropriate algorithm 
for accepting presorted subsequences). If it takes 2 years to 
come up with an unstable sort faster than Timsort, then it seems 
like a long time to be using something that isn't the best that 
we currently have. Especially if D is to be used in benchmarks 
against other languages.

Timsort is implemented now and has no real cost to use as 
default. If, at some point, an unstable sort is discovered that 
is faster on average than Timsort AND (extremely important) it 
has no potential for an attacker to be able to choose a sequence 
to sort that causes poor performance, then unstable could be 
switched back as the default at some point.

Right now, this could, in fact, cause a security hole (DOS-type 
attack) depending on how it is used. I think it's better to use a 
safer default in this case, even if we could make it faster than 
Timsort somehow.