BrowserUk has asked for the wisdom of the Perl Monks concerning the following question:

Question withdrawn in protest.

Not at the loss of (currently -1) XP--else I wouldn't have taken this step as it will no doubt attract even more this way.

It is a protest at the mentality of people that either:

Either way, I thought this place had seen the back of that mentality a while back. Seems not.

(And no, I still haven't found the answer, despite having downloaded and waded through the 1.8 MB Changes5.6. If it is in there, it's hiding!)

Replies are listed 'Best First'.
Re: 5.6.2 sort method
by davido (Cardinal) on Feb 24, 2004 at 05:25 UTC
    Hmm, I'll try to imagine what the original question was:

    Q: What sort method does Perl 5.6.2 use in its sort function?

    The best answer I found was in perl570delta under the "Performance Enhancements" heading:

    sort() has been changed to use mergesort internally as opposed to the earlier quicksort. For very small lists this may result in slightly slower sorting times, but in general the speedup should be at least 20%. Additional bonuses are that the worst case behaviour of sort() is now better (in computer science terms it now runs in time O(N log N), as opposed to quicksort's Theta(N**2) worst-case run time behaviour), and that sort() is now stable (meaning that elements with identical keys will stay ordered as they were before the sort).

    Also in perldoc -f sort for Perl 5.8.1 I found the following paragraph:

    Perl 5.6 and earlier used a quicksort algorithm to implement sort. That algorithm was not stable, and could go quadratic. (A stable sort preserves the input order of elements that compare equal. Although quicksort's run time is O(NlogN) when averaged over all arrays of length N, the time can be O(N**2), quadratic behavior, for some inputs.) In 5.7, the quicksort implementation was replaced with a stable mergesort algorithm whose worst case behavior is O(NlogN). But benchmarks indicated that for some inputs, on some platforms, the original quicksort was faster. 5.8 has a sort pragma for limited control of the sort. Its rather blunt control of the underlying algorithm may not persist into future perls, but the ability to characterize the input or output in implementation independent ways quite probably will. See the sort manpage.

    I hope this helps. ...IMHO, it was a good question, though admittedly I'm going strictly from imagination since I didn't see it before it was "retracted."


    Dave

[reply]
Re: 5.6.2 sort method
by ysth (Canon) on Feb 24, 2004 at 03:45 UTC
    5.6.2 uses a quicksort only, but its not the C library one (which is prone to segfaulting on too many platforms).

    Remember that occasionally people select the wrong vote button without realizing it.

[reply]
Re: 5.6.2 sort method
by jweed (Chaplain) on Feb 24, 2004 at 04:15 UTC
    Would it be possible to repost the original question, B. Uk? Since sorting is something that I'm pretty interested in, I would be very keen on hearing the question and its solutions (and maybe even take a crack at it myself).

    Some people do downvote questions, but I think that the whole community learns when one is posted, not just the one who posted it. I would really enjoy seeing it back.



    Code is (almost) always untested.
    http://www.justicepoetic.net/
[reply]
[reply]
Re: 5.6.2 sort method
by flyingmoose (Priest) on Feb 24, 2004 at 03:52 UTC
    Just think of this -- if you didn't reload PerlMonks so much, someone would have upvoted your node back to zero, and you would have never noticed. Don't worry about it, dude!
[reply]

Back to Seekers of Perl Wisdom