Burrows-Wheeler transform

An archiver shuffles a message before compressing it, because the shuffle gathers equal characters into clumps that pack well. It appends a $ terminator to the message, a character the message itself never contains, then lists every rotation of the terminated text, sorts that list, and keeps only the final character of each rotation, read from the top of the sorted list to the bottom. Those kept characters, joined in that order, are the code it files away. Messages hold lowercase letters and digits only, and both sort after $, so ordinary character order is all the sort ever needs. Given the code, return the message the archiver began with, without the terminator. An empty code came from no message at all, so return the empty string.