Re: [Fwd: Re: [FWP] sorting text in human-order]

[Uri Guttman <uri@sysarch.com>]

>>>>> "JSD" == Jonathan Scott Duff <duff@cbi.tamucc.edu> 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  ---------  uri@sysarch.com  ----------  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

==== Want to unsubscribe from Fun With Perl?  Well, if you insist...
==== Send email to <fwp-request@technofile.org> with message _body_
====   unsubscribe