>>>>> "JSD" == Jonathan Scott Duff <[EMAIL PROTECTED]> writes:
JSD> On Mon, Jan 01, 2001 at 04:31:42PM -0600, Jarkko Hietaniemi wrote:
>> (1) Quicksort has a weak point where it goes deep into the Quadratic Land:
>> (nearly) already ordered data. No, that is not so far-fetched a case.
>> Mergesort has no similar weakpoints: its performance is in fact
>> consistently N log N.
>>
>> (2) Mergesort is stable. Quicksort is not.
JSD> I figured it was something like this, but wanted to know if there
JSD> were any other reasons.
JSD> I recently tracked down a bug in some software that we've been using for
JSD> years that turned out to be an implicit assumption that perl's sort
JSD> would be stable when, of course, it's not. Had perl 5.7 come along
JSD> sooner I might never have caught the bug or been bitten by it :-)
there was a thread the other day in c.l.p.misc about this very
issue. regardless of the stableness of perl's internal sort, you should
never assume stability unless it is specified. perl5 never specified
this and relying on 5.7 for it is foolish IMO. adding sort stability is
not hard even with an unstable sort algorithm.
on this note, i then propose that we do specify perl6's sort to be
stable. we can at this point do that and by keeping our sort algorthm
choices to stable ones, we can deliver it. i would never sepc perl5's
sort as stable due to all the older versions out there with unstable
quicksorts.
uri
--
Uri Guttman --------- [EMAIL PROTECTED] ---------- http://www.sysarch.com
SYStems ARCHitecture, Software Engineering, Perl, Internet, UNIX Consulting
The Perl Books Page ----------- http://www.sysarch.com/cgi-bin/perl_books
The Best Search Engine on the Net ---------- http://www.northernlight.com
