develooper Front page | perl.beginners | Postings from February 2009

Re: perl sort

Thread Previous
From:
Raymond Wan
Date:
February 7, 2009 20:04
Subject:
Re: perl sort
Message ID:
498E59B9.9080008@kuicr.kyoto-u.ac.jp

Hi Marion,

Marion McCoskey wrote:
> While looking at the documentation for the sort function, I noticed it
> complaining about the shortcomings of the quick sort.  I share that
> feeling and I have developed a single-buffered count sort that is
> faster than the quick sort and a lot more stable.


Actually, the documentation states that from v5.7 of Perl, quicksort has been replaced with mergesort (see http://perldoc.perl.org/functions/sort.html).

But, in general, I wouldn't look too deeply into that documentation as every document seems to complain about quicksort.  :-)  I don't think its meant to "complain" but just to warn people of the short-comings of quicksort.  I presume that Perl originally made use of quicksort because of its existence in the C standard library...

And BTW, your web site seems complete but I honestly didn't look through it all.  AFAIK, linear sorting algorithms make assumptions about the data while comparison sorting algorithms do not [Cormen et. al. 2003 explains this better than me...]  So, in terms of a library function that needs to be general for all, something like quick/merge/heapsort seems to be better (plus, they are described in most algorithms textbooks).  So, for its shortcomings, I think these algorithms are here to stay...

Ray




Thread Previous


nntp.perl.org: Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About