Stable sorting in Perl

[sweetblood]

Is there a way to specify a stable sort? That is a sort where the non-keyed fields remain in natural order after the sort(fifo). I am of course presuming that Perl’s default behavior would be a more efficient unstable sort. If my assumption is incorrect then is there a way to specify an unstable sort to increase sorting performance?

[liz]

This might be an answer to your question. From perldoc sort:

NAME
       sort - perl pragma to control sort() behaviour

SYNOPSIS
           use sort 'stable';          # guarantee stability
           use sort '_quicksort';      # use a quicksort algorithm
           use sort '_mergesort';      # use a mergesort algorithm
           use sort 'defaults';        # revert to default behavior
           no  sort 'stable';          # stability not important

           use sort '_qsort';          # alias for quicksort

           my $current = sort::current();      # identify prevailing algorithm

Liz

[tye]

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
    ];

For a more complex form of sort:

# 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;
        ];
    };

Note that this allows us to avoid the RESTORE() step which often means that the XFORM() step becomes much simpler.

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:

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

Which may become my favorite sorting technique because it gives you almost maximum speed while not requiring RESTORE() (which is often the hardest part).

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

(updated.)

                - tye

[wirrwarr]

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

Both sorts are not stable.

daniel.

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

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

[sweetblood]

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

[sweetblood]

I saw a reference to that pragma somewhere on the internet however I don't get that when I do "perldoc -f sort". If I try use sort 'stable'; (et-al) I get: "Can't locate sort.pm ..." etc.
Do I have to have a seperate sort.pm from cpan? Or (and maybe this is most likely) is this not available in perl v5.6.0?
But thanks for the reply. ++

[liz]

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