This may work:

my @pretty = sort
{
   my @a = $a =~ /^(.+?)(\d*)$/;
   my @b = $b =~ /^(.+?)(\d*)$/;
   return ( $a[0] cmp $b[0] ) ||
         ( $a[1] && $b[1] && $a[1] <=> $b[1] ) ||
         ( $a[1] && 1 ) || ( $b[1] && -1 );
} @not_so_pretty;
[download]

I changed the regular expressions to ensure that the entire name is captured (^ and $). I also changed them such that words that aren't suffixed by numbers still match (\d*). Finally, although, I'm not sure if this is important for your situation, I changed them such that any characters before the number suffix are allowed (.+?). The return is more complicated since it now handles the case where the $a[1] or $b[1] may not be defined since the word doesn't contain a numeric suffix.

Update: go with dragonchild's approach which is more concise and clear. However, do consider if any words may contain number other than as a suffix and decide how you want to handle this case (my code sorts these alphabetically).