Well, let's be clear about what's happening.
As a general rule, associative arrays, as implementations of the abstract data type known as Map or Table, are fundamentally unordered, regardless of the implementation details. It's true that some implementations naturally keep the keys in a recognizable order (e.g. binary trees in lexical order by key, association lists in insertion order), while others (such as hash tables) do not, but such details don't necessarily dictate the features of any given implementation.
Most systems with associative arrays don't provide a mechanism to retrieve the elements in a specified order. Some do – Ksh93+ was brought up, and I mentioned _javascript_, PHP, Python, and Ruby. Sometimes this is an actual feature and other times an accidental detail; in Clojure, maps that are small enough (less than about eight pairs) are stored using a data structure that keeps the keys in lexical order, so you might be lulled into thinking that's true generally, but larger maps use a hash table and revert to a seemingly unordered state.
Zsh has expansion flags that let you get either the keys ( k ) or the values in lexical order, ascending ( o ) or descending ( O ).
Unfortunately it does not have a way to get the keys and values simultaneously in any sort of meaningful order while maintaining the pairwise association. If you use both flags k and v together with either o or O, you will get an undistinguished muddle of keys and values all sorted together into one big list.
Which is a consequence of the way the flags work. With no flags, an array expands to its values. The k flag says "get the keys instead". The v flag says "include the values, too". The resulting list alternates between keys and values, but it is still a flat, one-dimensional array; it has no internal structure keeping the pairs together. The sort triggered by the ordering flags has no way to know that it's a list of pairs.
You could make the case that it should know that based on the flags; the flag triplets kvo and kvO could order just the keys while maintaining the pairwise association with their values, as a special case. Though that privileges the keys over the values; might one not also conceivably want to sort by value while maintaining the associated keys?
In fact, as far as I can tell, there's currently no good way to get from a value to its associated key at all. If you want the key/value pairs in order with current zsh, there is a ready solution: simply iterate through the sorted keys returned by ko and use them to get the associated value:
for key in "${(@ko)array}"; do
... something with "$key" and "${array[$key]}" here ...
done
But if you instead iterate through the values (with or without o), there's no analogous way to get back to the corresponding key. Maybe that's the missing functionality we should look into instead: inverting an associative array. Of course duplicate values are troublesome in this regard.