Your claim that the sorted version keeps all the information is false-- it is impossible to reverse the transformation.

I'd love to see this with the Burrows-Wheeler-Transform (suffix sorting), which doesn't actually lose any information-- it might even be possible for a human to (very) slowly read it.

I particularly liked your "WHY" section.

awesome :-)