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.)