The best sorting algorithm of Java – burrows Wheeler transformation (BWT)

Burrows Wheeler transformation got me into some problems This is a university project, but it is only a small part of it The whole project consists of three different algorithms for data compression

I just want to find out what is the most memory and time-saving sorting algorithm for suffix sorting in burrows wheel transformation? Coding needs to be as efficient as possible

For smaller arrays, sorting doesn't really work, but when our compressed text files become larger and larger, the time consumed by using inefficient sorting algorithms will actually destroy the efficiency of time and memory

Any help will be greatly appreciated. Thank you in advance!

edit

We write code in Java, only to realize that I never mentioned it

Solution

Many BWT based utility compression tools are based on divsufsort and msufsort But their o (n ^ 2) performance is the worst. You must use some preprocessing methods for the data before sorting

In theory, for the best time / space cost, try SA is and SA DS

If you are trying to write your own suffix sorting algorithm, I suggest you start with the quick and simple qsufsort