If you wanted to go down that line of thinking, you should be able to use a hash function to uniformly shuffle the keys within a larger space, and then apply yo

If you wanted to go down that line of thinking, you should be able to use a hash function to uniformly shuffle the keys within a larger space, and then apply your sort to that. No need to store the randomized keys. Probably performance wouldn't be as good as the OP article though.