Worst-case performance of quickSort / getPivot

[Andrei Alexandrescu]

On 11/16/13 2:11 PM, Xinok wrote:
> On Saturday, 16 November 2013 at 20:35:21 UTC, Andrei Alexandrescu wrote:
>> On 11/16/13 11:46 AM, Xinok wrote:
>>> * Regardless of these improvements, I think Timsort should be the
>>> default sorting algorithm. It's the better choice in many (most?) cases
>>> and, well, it's stable. Quick sort would still be available for those
>>> cases in which it's faster and stable sorting isn't needed.
>>
>> There's something fishy about a more restricted algorithm doing better
>> than one that's less restricted. We must improve unstable sort, not
>> make stable sort the default.
>>
>> Andrei
>
> Timsort is an "adaptive" sort. It's able to achieve better performance
> in many cases by exploiting patterns in the data.

This is in response to what? Are you trying to talk me out of the 
pigeonhole principle?

> I decided to make a nice little test using my benchmark code here:
> https://github.com/Xinok/XSort/blob/master/benchsort.d

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