I wrapped all of the routines in @{[...]} to provide the list context; that was what I'd used in the preamble tests.

I added an STss as I had indicated this morning. I decided that STmcs was going to be pretty much the same as STss, so I skipped that one. I did add an mcse which was mcs with map BLOCK replaced by map EXPR.

sub st_sort_substr {
    @{[
        map $_->[0],
        sort {
            $a->[1] <=> $b->[1]
        }
        map [$_, substr $_, 2], @unordered
    ]};
}

sub map_cat_substr_expr {
    @{[
        map "a-$_",
        sort {
            $a <=> $b
        }
        map substr($_, 2), @unordered
    ]};
}
[download]

I saw ++swl's post. There wasn't any code there, so I guessed.

use Sort::Key 'ikeysort';
use Sort::Key::Natural 'natsort';
...
sub sort_key_integer {
    @{[
        ikeysort { substr $_, 2 } @unordered
    ]};
}

sub sort_key_natural {
    @{[
        natsort @unordered
    ]};
}
[download]

I ran the benchmark several times; there were no major differences between runs. Here's a sample output, in the spoiler; it's getting very wide (18 subroutines now) and this post is "Re^7", so probably best viewed via the "download" link.

And here's the code: