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

Re: perl sort

Thread Previous
Raymond Wan
February 7, 2009 20:04
Re: perl sort
Message ID:

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

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...


Thread Previous Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at | Group listing | About