use Sort::Key qw(keysort);

sub mkkey {
    my $key = deaccent $_;
    $key =~ s/(?<=\d)\Q$separator\E(?>=\d)//g;
    $key =~ s{0*(\d+)}{
        my $len = length $1;
        "\x00" . ('9' x ($len / 9)) . ($len % 9) . $1
    }eg;
    $key;
}

...

cmpthese(
    -30,
    {
        #'alphanum'        => sub { @temp = sort { alphanum( $a, $b ) } @array; },
        #'Sort::Naturally' => sub { @temp = nsort(@array) },
        'natural_sort'    => sub { @temp = natural_sort(@array) },
        'Sort::Key' => sub { @temp = keysort \&mkkey, @array },
    }
);