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

[perl #119635] deprecate and remove qsort?

Thread Previous | Thread Next
Father Chrysostomos via RT
September 12, 2013 15:26
[perl #119635] deprecate and remove qsort?
Message ID:
On Thu Sep 12 05:54:17 2013, nicholas wrote:
> 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.

But would it be possible for perl to detect datasets that work better
with qsort?  Or (most likely) would the time the detection takes
outweigh the benefits?


Father Chrysostomos

via perlbug:  queue: perl5 status: open

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