Ok, we've got a problem of terminology here: You have a hash (perl) which contains keys and values. Your data is filenames and hashes of the files. The keys of your hash (perl) are the hashes (file) of your files. The names of the files are the values of the hash (perl).

Here is your data structure:

%file_hashes = ( $hash1 => $filename1,
                 $hash2 => $filename1, );
[download]

This means that keys returns ($hash1, $hash2). And that ($file_hashes{$hash1} eq $filename1).

So, when you type sort { $file_hashes{$a} cmp $file_hashes{$b} } keys %file_hashes you are sorting your list of hashes (file) by the values of the hash (perl). Which are your filenames.

You want to sort the list of hashes (file). Which is the keys of your hash (perl). Which is sort keys %file_hashes. Try it. It will work.

Then go read perldata five or six times. It's not the best introduction to the subject (it's designed more as a reference), but it is thorough.