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

The Effect of sort on Equal Items

by Dr. Mu (Hermit)
on Oct 03, 2002 at 04:01 UTC ( #202438=perlquestion: print w/replies, xml ) Need Help??

Dr. Mu has asked for the wisdom of the Perl Monks concerning the following question:

Does sort come with any documented guarantee that the original order of "equal" items will be preserved? If so, can this behavior be counted on to persist from one version of Perl to the next? If not, is there a better way to do so than the following?
@sorted = sort {&foo($orig[$a]) cmp &foo($orig[$b]) || $a <=> $b} (0 . +. @orig - 1)
where &foo returns the field or aspect of each item being sorted on (and where a Schwartzian Transform would be performed if @orig is sufficiently long and &foo is sufficiently complicated).

(The best answer will end up as a margin note in my camel book.)

Replies are listed 'Best First'.
Re: The Effect of sort on Equal Items
by BrowserUk (Pope) on Oct 03, 2002 at 04:15 UTC

    This may answer most of your question:

    It includes 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.


    Cor! Like yer ring! ... HALO dammit! ... 'Ave it yer way! Hal-lo, Mister la-de-da. ... Like yer ring!
Re: The Effect of sort on Equal Items
by Zaxo (Archbishop) on Oct 03, 2002 at 04:39 UTC

    To add to BrowserUK's answer, mergesort is stable, producing the original order for items that compare equal. Quicksort is not stable, the sorted order is scrambled for equal items.

    In the perl 5.8.0 source tree, the sort algorithm is found in pp_sort.c. That file has unusually good comments in it. Here is the meat of perl's top level sort function, Perl_sortsv():

    hints = SORTHINTS(hintsv); if (hints & HINT_SORT_QUICKSORT) { sortsvp = S_qsortsv; } else { /* The default as of 5.8.0 is mergesort */ sortsvp = S_mergesortsv; } sortsvp(aTHX_ array, nmemb, cmp);

    After Compline,
    Zaxo

      Thanks to both! Yikes! Looks like that "margin note" is gonna hafta be a link. ;-)

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (4)
As of 2020-11-28 08:47 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?