At the heart of the Burrows--Wheeler transformation is any basic string sorting algorithm. This is the implementation of two different string sorting algoirthms, plus one variation to pin down the most efficient one of the three; a least signficant digit suffix sort (LSD), a recursive most signficant digit suffix sort (MSD), and a multi--threaded version of the latter. All three share auxilary arrays for implementing a simple count sort. MSD differs from LSD in that it is recursive, and adjacent recursive calls at each level of recursion are indepedent of one another, allowing for multithreading.
In theory, the recursive MSD algorithm is faster than LSD, and the multithreaded version should be magnitudes faster than both. In reality, there was not much difference in terms of speed between any of them. This (I think) is a direct consequence of the auxilary arrays in the count sort algorthm embedded within all three; the memory store is the bottleneck. Even with efficient explotation of cache memory, this will not mitigate the issue. This exercise ultimately served to demonstate how a simple 256 long array can hamstring an entire chain of reasoning.
The code and the program can be found here:https://github.com/Adhamkmopp/Burrows-Wheeler. It takes a simple text file as input, and outputs the transformed text for each of the three different passes. Some additional notes are included in the link as well.