Your code doesn't work because you forgot return $key; in normalize_digits.

Also, I think you can speed things up by using the following:

my @sorted = map { local $_ = $_; s/^.*\0//; $_ }
             sort
             map { normalize_digits($_) . "\0$_" }
             @data;
[download]