The sort transformation is an alternative to the Burrows-Wheeler transformation described in Wheelers article or Mark Nelsons article.
This transformation features a fast and deterministic in time alternate approach that could be implemented in hardware easily. For more information see the original paper presented at the DCC97 or patent application ur US patent 6,199,064. (both links go to external sites - please inform me if broken)
This algorithm is protected by US patent 6,199,064, others pending.
Available at this page is (
The compression program szip uses this sort and allows you to experiment with various orders.
A remark on the comp/decomp source code: the comments at the beginning are not accurate, it actually uses 2 MTF models before the full model and a cache of size 30. However for historical reasons I made the original source available. If there is interest I can also make the source available with unix linefeeds and as .tar.gz instead of .zip.
(c) Michael Schindler, April 2000.
If you locate a spelling error click here