Not sure how you "sort" a hash (other than somehow using the list output by sort {...} keys %hash).

Completely untested, just an idea:

@sorted = map { join "", @$_ }
          sort { no warnings qw/numeric uninitialized/;
                 (grep $_, map { $a->[$_] <=> $b->[$_] ||
                                 $a->[$_] cmp $b->[$_] }
                               0..($#$a+@$b)
                 )[0] || 0
               }
          map { [ split /(?<=\d)(?=\D)|(?<=\D)(?=\d)/, $_ ] }
          @array;
[download]

Update: oops, left the array indexes off $a and $b