Quadratic time to sort in a simple case?

[Andrei Alexandrescu]

On 4/19/13 6:37 PM, Ivan Kazmenko wrote:
>> That [SwapStrategystable] uses the TimSort that contains
>> the optimization you look for.
>>
>> alias mySort = sort!("a < b", SwapStrategy.stable);
>
> Thank you, these are good for now.
>
> 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?

Yah, that would mean one can't reason what a piece of code does without 
knowing what the context was.

>>> Consider a sorted array. Append an element that is less than all the
>>> previous elements. Then sort the array again by the sort function
>>> from std.algorithm.
>>
>> If you know that, then don't do a sort. Make some free space in
>> the array, shift the items, sort just the first part with a slice.
>
> That behavior isn't always easy to predict.
>
> 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.

I could have sworn I made getPivot choose at random at some point. I 
agree this should be fixed; there are a number of possibilities:

a) choose median of five

b) if the array is large, sort a stride of it first (e.g. 1%) then 
choose the pivot as the median point of that stride

c) add introspection to the algorithm, i.e. if an attempt to partition 
hits the worst case or near worst case, just try another pivot instead 
of moving forward with the sorting stage.

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

That view of safety is different (memory safety).

> In this particular case, that would mean having a worst-case O(n
> log n) sort, and/or a stable sort, by default - but with the opportunity
> to switch to the (time-wise and stability-wise) unsafe quicksort if you
> really need the extra speedup and know what you are doing. So, why isn't
> TimSort the default?

TimSort is slower on average.


Andrei