Beefy Boxes and Bandwidth Generously Provided by pair Networks
"be consistent"
 
PerlMonks  

Re^2: how sort works

by JavaFan (Canon)
on Mar 07, 2011 at 17:18 UTC ( [id://891859]=note: print w/replies, xml ) Need Help??


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

Note that the mergesort implemented by Perl isn't the stock mergesort you see in the textbooks.

It's a special version of mergesort that takes advantage of runs of already sorted (or reversed sorted) items. While at the same time making sure the sort is stable. This makes sorting of (almost) sorted lists faster than stock mergesort would give you.

The quicksort implemented by Perl has some defenses against poor performance as well. Traditional quicksort is behaves quite poorly on sorted lists (with naive textbook implementation even going quadratic). Perls quicksort does some smart pivot picking (middle-of-three, IIRC) - but it can still behave badly on pipe-organ shaped lists. As an extra defense, if quicksort is picked, and the list is larger than a certain size, the list will be shuffled first.

Replies are listed 'Best First'.
Re^3: how sort works
by tilly (Archbishop) on Mar 08, 2011 at 07:35 UTC
    Do you know whether Perl's mergesort has borrowed a lot of ideas from Python's timsort?
      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
Domain Nodelet?
Node Status?
node history
Node Type: note [id://891859]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others rifling through the Monastery: (5)
As of 2024-03-29 00:28 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found