This works assuming that the numbers are on the end, there are no leading 0's, and there are at most 5 digits (if more, it's easy to see where to adjust):
my @pretty = map {s/(?<=\D)0+//; $_}
sort
map {chomp; do {no warnings; sprintf "%s%05d", /(\D*)(\d*
+)/}}
@not_so_pretty;
The first map (that is, the bottom one in the code), normifies the strings, by padding 0's so all the numbers have equal length - if there are no trailing numbers, 0's will be used. Then we perform a regular sort, and finally, we strip off the leading 0's (which could mean all the 0's).
This technique is one of the variations of the GRT.