I agree. If I pass a list into someone else's function, I want at least a warning in the docs if it's going to modify it.

Please recheck this solution. Since xs is a reference to a list outside of the function, it has the side affect of modifying the data structure. That could be a nasty surprise to the user of this function. I believe a better solution is to run the sort on a copy of the list.