Quadratic time to sort in a simple case?

[Andrei Alexandrescu]

On 4/22/13 5:52 PM, bearophile wrote:
> Andrei Alexandrescu:
>
>> 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.
>
> Or switch to a sort that is guaranteed to have a pseudo-linear complexity.
> I am not sure, but I think the C++ STL sort does this.

There's not "the C++ STL sort". Any implementation is fine as long as it 
has O(n log n) expected run time.

>> TimSort is slower on average.
>
> Here it's not easy to define what "average" is. Python devs think that a
> common case is an array with mostly sorted data with unsorted data at
> the end.

Note that in this case it's sorted data followed by its smallest 
element. (Changing the value does improve sped.) This is hitting a 
corner case: median of 3 will pick the smallest element, which will lead 
to an inefficient partition. I haven't looked at the code, but it seems 
the smallest element again makes it to the beginning and the end of the 
array so it's again picked etc.

One simple solution to this (which I forgot to mention) is picking a 
pivot at random.


Andrei