I was indeed thinking of (1), albeit just using radix sort - your permutation trick is nicer. But (2) doesn't work in general, because information theory may n

I was indeed thinking of (1), albeit just using radix sort - your permutation trick is nicer. But (2) doesn't work in general, because information theory may not allow storing more information in the input array than is already there; I'm convinced myself, but I haven't come up with a better argument than "obvious" in the time I had available. ;-)