Since François is probably waiting for a pronouncement for me, let me say that I think this is a problem that should not be addressed by changes to the language, builtins or library.
A sorted() method for lists would require a copy. François argues that the extra space could be used by the sorting algorithm. But if the requirement is that the original array must not be shuffled at all, I expect that there's no way you can make use of the extra space: you have to make a copy of the whole list first, which then gets shuffled in various ways. I suppose it would be possible to write a sorting algorithm that made some use of the availability of an output array, but rewriting the sort code once again so that you can avoid writing a three line function doesn't seem a good trade-off.
More generalized solutions seem overkill: I've not seen demand for sorting other container types (except for list subclasses).
The argument against making sort() return self (while sorting in-place) still holds, and this argument also means that having a sorted() that sorts in-place is a bad idea.
You could consider adding a "sort" option to keys(), values() and items(), but that doesn't solve other similar cases.
I think you'll just have to live with it. Or you can create a dict subclass that sorts its keys.
--Guido van Rossum (home page: http://www.python.org/%7Eguido/)