Re: how sort works

Depending on your version of perl, it may use a quicksort or a mergesort. (Google those algorithms and you'll surely find some very good explanations of both.) Newer versions give you some say over which is used via the sort pragma.

-sauoq "My two cents aren't worth a dime.";

Comment on Re: how sort works

Replies are listed 'Best First'.
Re^2: how sort works by JavaFan (Canon) on Mar 07, 2011 at 17:18 UTC
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.	[reply]
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?	[reply]
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.	[reply]