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)

[download]
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 (Patriarch) 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!
[reply]
[d/l]
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);

    [download]

    After Compline,
    Zaxo

[reply]
[d/l]
      Thanks to both! Yikes! Looks like that "margin note" is gonna hafta be a link. ;-)
[reply]

Back to Seekers of Perl Wisdom