In case you aren't on the leading edge of Perl versions and don't have sort.pm, you can get a stable sort fairly easily:

# Replace:
    my @sorted= sort @list;

# with:
    my @index= sort {
        $list[$a] cmp $list[$b] || $a <=> $b
    } 0..$#list;
    my @sorted= @list[@index];

# or with (to avoid @index remaining in scope):
    my @sorted= @list[
        sort {
            $list[$a] cmp $list[$b] || $a <=> $b
        } 0..$#list
    ];
[download]

# Replace:
    my @sorted=
        map { RESTORE($_) }
        sort { COMPARE($a,$b) }
        map { XFORM($_) }
        @list;

# with:
    my @sortOn= map { XFORM($_) } @list;
    my @index= sort {
        COMPARE($sortOn[$a],sortOn[$b]) || $a <=> $b
    } 0..$#sortOn;
    my @sorted= @list[@index];

# or with (to avoid temporaries remaining in scope):
    my @sorted= do {
        my @sortOn= map { XFORM($_) } @list;
        @list[
            sort {
                COMPARE($sortOn[$a],sortOn[$b]) || $a <=> $b
            } 0..$#sortOn;
        ];
    };
[download]

If you are going for speed by avoiding COMPARE() [the advantage of which has been reduced (but not eliminated) for some cases due to new optimizations], then consider:

# Replace:
    my @sorted=
        map { RESTORE($_) }
        sort
        map { XFORM($_) }
        @list;

# with:
[download]

    my @sorted= @list[
        map { unpack "N", substr($_,-4) }
        sort
        map { XFORM($list[$_]) . pack "N", $_ }
        0..$#list
    ];
[download]

I like it so much, I've made it an official snippet: fast, flexible, stable sort.

(updated.)

Sorry, maybe I just don't get it, but why is your first example a stable sort?

my @unsorted = 
  ([1,1], [2,1], [1,2], [2,2], [2,3], [1,3], [2,4], [1,4]);

print join( ' ', 
  map { $_->[0].$_->[1] } 
    sort { $a->[0] <=> $b->[0] } @unsorted) . "\n";

my @sortedindices = sort 
  { $unsorted[$a]->[0] <=> $unsorted[$b]->[0] } 
  0..$#unsorted;

print join ( ' ', map { $_->[0].$_->[1] } 
  @unsorted[@sortedindices]);
__END__
11 12 13 14 23 21 24 22
11 12 13 14 23 21 24 22
[download]

Both sorts are not stable.

daniel.

update: got it now ;-) replace compare-function by

$unsorted[$a]->[0] <=> $unsorted[$b]->[0] || $a <=> $b
[download]

This is perfect ... I'm going to pin this to the wall of my cube! ++

tyes node is one of the better collections of the various advanced sorting techniques that I've seen. However you may want to have also have a look at one of PM's earliest nodes, and the canonical Schwartzian Transform (ST), which is the term generally given to most of these techniques in books. There is also the Guttman Rosler Transform (GRT) which is IMO a specialisation of the ST, and of which class I would say that tyes variant belongs to, although I suspect that perhaps it deserves its own name, possibly the Tye Transform? :-)


---
demerphq

_{<Elian> And I do take a kind of perverse pleasure in having an OO assembly language...}

There is a subtle difference between:

perldoc sort

and

perldoc -f sort

The former gives you the documentation of the sort pragma, whereas the latter gives you the documentation of the sort function. But indeed, you appear to need at least 5.8.0 for the sort pragma.

Liz

Ahhh... When I do perldoc sort I get "No documentation for sort..." So only perldoc -f sort gives me anything. I think you're right, I must need 5.8.0 or better for the sort pragma. Thanks!