I find it interesting that after so many decades with concepts of object oriented programming and encapsulation being current that there is not a clearer distinction between the behaviors of the interfaces to arrays and hashes and the internal implementation details.

So if keys sorted the keys before returning them, the hash would be considered sorted? nah.

Absolutely! For most users of perl a hash is (and should be) characterized by the behaviours of its interfaces. If the usual interfaces provide the contents in sorted order, then the hash is sorted, from a user perspective.

The common interfaces for accessing a hash collectively (i.e. not lookup of individual values) are: flattening to a list and the keys, values and each functions. If these returned the contents in sorted order (for some definition of sorted order) then most users of perl would consider the hash to be sorted. Whether, internally, it was implemented as an array with linear lookup, hashed bucket lists, B-tree, a convoluted, permutated, obfuscated collection of bits or whatever, would be, as it should be, irrelevant.

As it is, the usual interfaces return the contents in an order that is difficult for most users to predict and understand and which is quite variable as the contents changes. This unpredictability of the order of results (and from a naive user perspective they are very unpredictable, despite the generally deterministic nature of most modern computers, and more so since the randomization was introduced to enhance security) leads directly to the conclusion that hashes are unsorted. And this conclusion is strongly reinforced by the common use of sort, as in sort keys %hash. The sort function is not particular to hashes and is rightly perceived as something done to the unsorted list of hash keys returned by keys, not an integral part of the hash interface.

Of course, for the implementers of perl, the internals are very important. But for users they are only indirectly important to the extent that they affect the performance with which the provided interfaces deliver their results.

What makes an array sorted and a hash unsorted?

The user interfaces.