That's one of the reasons radix sort is terribly quick when applicable (and a lot of orderings are lexicographic). It's effectively just a few scans over the data. I suppose the simplest version does make a copy of the data but it has excellent locality of reference.