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;
[download]

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.