Quadratic time to sort in a simple case?

[bearophile]

Ivan Kazmenko:

> A seemingly easy way to provide the choice globally would be to 
> have an assignable SwapStrategy.default in std.algorithm... or 
> would that be a bad design decision to have such a global state?

With that I think there is no way to write a pure sort. Hopefully 
someday the sort() will be pure. Generally global mutable state 
is bad to write unittests, and to reason about code. So I don't 
think Andrei will do that. It's not kosher.


> Still, I think this is a problem in Phobos which should be 
> fixed.
>  In most implementations of quicksort (even middle-element, the 
> easiest to come up with), one expects it to perform in O(n log 
> n) with probability close to one, except on some artificially 
> constructed cases.
>
> On a side note, I'm surprised that median-of-three (getPivot in 
> std.algorithm) fails at such a simple test, so I had something 
> new to learn there, too.  If I just comment out the switch in 
> getPivot and "return mid" directly, it becomes fast enough in 
> this case.

Your case is a common one, so I think this problem should be 
studied a little better. I suggest to write a little better 
benchmark that shows the problem, and put it in Bugzilla. At 
worst it will be closed with wontfix.


> Another view at this is the following.  As far as I know by 
> now, one of the points beyond D (and Phobos) design is to have 
> everything safe by default, but faster if you want it 
> explicitly and you know what you are doing.

Right, but I think that D Zen rule is mostly about things like 
memory safety, etc.


> 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).

Bye,
bearophile