Re^2: Stable sorting in Perl (old)

in reply to Re: Stable sorting in Perl
in thread Stable sorting in Perl

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]

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;
        ];
    };
[download]

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:
[download]

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

In Section Seekers of Perl Wisdom