Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
PerlMonks  

Re^3: how sort works

by tilly (Archbishop)
on Mar 08, 2011 at 07:35 UTC ( #891962=note: print w/ replies, xml ) Need Help??


in reply to Re^2: how sort works
in thread how sort works

Do you know whether Perl's mergesort has borrowed a lot of ideas from Python's timsort?


Comment on Re^3: how sort works
Re^4: how sort works
by JavaFan (Canon) on Mar 08, 2011 at 10:19 UTC
    I do not think so. John P. Linderman ported a C implementation of "Optimistic Merge Sort" by Peter M. Mcilroy to Perl. The comment in pp_sort.c says that this was presented at SODA '92, but that seems a typo. The ACM portal claims it was SODA '93. Citation. The article itself is downloadable - for a fee.

    Now it may very well be that timsort implemented the same algorithm, but I do not recall ever hearing any reference to timsort on the p5p mailing list.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://891962]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (5)
As of 2015-07-04 10:07 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (59 votes), past polls