Quadratic time to sort in a simple case?

[Dmitry Olshansky]

24-Apr-2013 01:09, Ivan Kazmenko пишет:
> And on Tuesday, 23 April 2013 at 01:10:26 UTC, Xinok wrote:
>> I filed a bug report for this issue a year ago:
>> http://d.puremagic.com/issues/show_bug.cgi?id=7767
>>
>> I've been meaning to fix this issue myself. Time allowing, I'll do it
>> soon.
>
> What I wonder now, what would be the goal of such a fix?
>
> One possible goal would be to have an O(n log n) worst case sort.  And
> that would perhaps cost some speed and/or memory on average.  Besides,
> such a sort function is already implemented (TimSort), so it's just a
> matter of setting the default then.

A good unstable sort can do the job faster (at the very least not 
slower) then a good stable sort.

I'm looking forward to a version of Introsort that Xinok has in mind as 
a "Q-sort fix".



-- 
Dmitry Olshansky