Assuming that you got the last two strings in your sorted example the wrong way around; Ie. '12h' should sort before '123' according to the logic of the rest of the example? (Ignore this if you didn't, but explain better :)

Using an ST. Transliterate the strings to map the characters to the collating sequence desired, sort and then discard the transliterated values:

@a = qw[  ased12 frtg Frth zdcs 123 12h awq ];;

print for map { 
    $_->[0] 
} sort{ 
    $a->[1] cmp $b->[1] 
} map{ 
    (my $t = $_) =~ tr[aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWx
+XyYzZ0-9]
                      [\x00-\x3e]; 
    [ $_, $t ] 
} @a;;

ased12
awq
frtg
Frth
zdcs
12h
123
[download]

Update: Actually, skip the ST. Just tranliterating on the way in and back again on the way out works out much (65%) quicker:

@a = qw[  ased12 frtg Frth zdcs 123 12h awq ];
print for map{
    tr[\x00-\x3e][aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ
+0-9];
    $_;
} sort map{
    tr[aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ0-9][\x00-\
+x3e];
    $_;
} @a;

ased12
awq
frtg
Frth
zdcs
12h
123
[download]