This is because hashes do not have a standard internal order, the returned order of keys or values is random, unless you sort them.

Correct, but keys, values, and each use the same order for the same hash. From perlfunc:

Entries are returned in an apparently random order. The actual random order is subject to change in future versions of perl, but it is guaranteed to be in the same order as either the keys or values function would produce on the same (unmodified) hash. Since Perl 5.8.2 the ordering can be different even between different runs of Perl for security reasons [...].

Alexander