Front page | perl.beginners |
Postings from February 2009
Re: perl sort
From: Raymond Wan
February 7, 2009 20:04
Re: perl sort
Message ID: 498E59B9.email@example.com
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...