develooper Front page | perl.perl5.porters | Postings from September 2013

Re: [perl #119635] deprecate and remove qsort?

Thread Previous | Thread Next
Nicholas Clark
September 12, 2013 12:53
Re: [perl #119635] deprecate and remove qsort?
Message ID:
On Fri, Sep 06, 2013 at 02:59:44PM -0400, John P. Linderman wrote:
> > Part of the reason, I think, was that v5.6 and earlier's sort was a
> > quicksort, and hence not a stable sort.
> Stability was definitely a feature, but my best argument to Jarkko was that
> far too many common sequences (organ pipe, sawtooth, etc.) went quadratic,
> and Peter Mcilroy's merge sort did a particularly nice job on sequences
> with pre-existing order (linear time on sorted input).
> The only sequences (that I could think of, anyway) where it was clear that
> qsort would outperform merge sort were those containing many repetitions of
> a small number (k) of keys.  Qsort's "fat pivot" guaranteed that only k
> passes would be required, where merge sort might need log N.

The bit that keeps bugging me is "how many people know that their data is
usually going to be in a particular form that qsort favours"?

In that, the amount of use cases where it's correct to specify qsort instead
of mergesort are small, the amount of effort needed to determine this is
high, and the gain itself is small?

In which case, seems that choosing a specific sort algorithm is not the
first place to look at optimising.

Nicholas Clark

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