my @g = qw[
    St1x7 St1x23 St10x355 Stb10x100 Sta2x9 St2x1 Stbbb12x5 Staaa12x4 St6x33333 
    St6x0 St8 St0x11111111111111 St0x22222222222222 AAAAAAAAAAAAAAAAAA ZZZZZZZZZZZ
];;

print for map{ 
    my $n = unpack 'N', substr $_, -4;  
    substr $_, $n, length() - $n - 4  
} sort map{ 
    (my $x = $_) =~ s[(\d{,9})][ pack 'N', $1]ge; 
    pack 'A*A*N', $x, $_, length( $x ) 
} @g;;

AAAAAAAAAAAAAAAAAA
St0x11111111111111
St0x22222222222222
St10x355
St1x23
St1x7
St2x1
St6x0
St6x33333
St8
Sta2x9
Staaa12x4
Stb10x100
Stbbb12x5
ZZZZZZZZZZZ