I am quite sure you have fallen into the Google group think of no sorting + no folders. Every time someone at google has the balls to challenge that dogma, like replacing "add label" with "move to" in Gmail, correct usage soars. The search & labels only fallacy has led to some terrible interfaces, such as the Google Docs home page.
I'm quite sure you're wrong on that, since I know exactly how we reached that conclusion despite originally thinking otherwise. I worked on the issue at another major net company where we were dealing with a _lot_ of lists being viewed by very large numbers of users. While I'm unfamiliar with the results of research at Google, both analytics of production services and follow-up user labs showed very little traction for using sort to reorganize sets of information among non-technical users.
It's just not how regular people think about manipulating information - in the real world, sorting a set of any interesting size is impractical if not painful. You can literally ask a loaded question - "is there any way you could sort those to make XYZ easier?" and folks will avoid that in favor of other method.
That is surprising, as I have data points that show people prefer clicking "least difficult", or "most popular" vs search or an alternative categorical method. I really think it comes down to context. You use the phrase "interesting size" and that is relevant, as I only consider sorting of stuff that is generated by a human, not humankind. I fully accept the interface should be different for human data versus humankind data. I think google products often assume every list is infinitely long, and it can lead to poor interface choices.
By "interesting size" I mean "large enough that it's no longer convenient to page through it." Generally, for less than that, sorting's not necessary because you can just scan through the list visually, and for longer than that, the sort generally becomes useless anyway. It didn't seem to matter if the list was 100 long or 100,0000 long.
We saw less than 10% of users ever employing the sort controls; that's not zero, but it's low enough that you can't depend on them to cover use cases.
The problem with your examples are that you're not really showing "sorts" from a user standpoint. What a user is really doing is effectively filtering for the "show me the N least difficult", not "sort by difficulty, ascending." Also, sorting on a relatively scaled value make more sense, but a lot of the time the values in a column don't have that kind of relationship. What's the "least zip code" good for?
