On 6/21/14, 8:28 AM, Xinok wrote:
On Saturday, 21 June 2014 at 09:19:19 UTC, Joseph Rushton Wakeling via
Digitalmars-d wrote:
I can't find the issue in bugzilla, but IIRC there was a problem with
unstable sort where it would produce worst-case-scenario behaviour in
the event of being given input that had only a few unsorted elements.
I ran into it when implementing some of the algorithms in Dgraph:
appending one new element to an array and using sort() would generate
quadratic behaviour.
That case of "mostly sorted" input seems to also be present in the
problem described here.
That has since been fixed. I implemented heapsort as a fallback
algorithm, effectively making it an introsort.
Wait, when did that happen? I think a better solution would be to take
median of more than 3 elements. -- Andrei
