For interest, I tried expanding the test to include the CPAN module Sort::Key, which basically does the same thing as an ST, only faster and without the confusing syntax. The pertinent part of the new code reads

use Sort::Key 'ikeysort';

sub sort_key {
    my $c = 0;
    my @s = ikeysort { $c += 1; /(\d+)/; $1 } @l;
    push @{$regexes{key}}, $c;
}
[download]

which is then passed to the tests in exactly the same way as the existing brute_force() and ST().

It works out about twice as fast as the ST on the shuffled lists, but is only about 10% faster than the ST on sorted lists, where brute force still wins.