On the Optimisation of the GSACA Suffix Array Construction Algorithm

The suffix array is arguably one of the most important data structures in sequence analysis and consequently there is a multitude of suffix sorting algorithms. However, to this date the \texttt{GSACA} algorithm introduced in 2015 is the only known non-recursive linear-time suffix array construction algorithm (SACA). Despite its interesting theoretical properties, there has been little effort in improving the algorithm's subpar real-world performance. There is a super-linear algorithm \texttt{DSH} which relies on the same sorting principle and is faster than \texttt{DivSufSort}, the fastest SACA for over a decade. This paper is concerned with analysing the sorting principle used in \texttt{GSACA} and \texttt{DSH} and exploiting its properties in order to give an optimised linear-time algorithm. Our resulting algorithm is not only significantly faster than \texttt{GSACA} but also outperforms\texttt{DivSufSort} and \texttt{DSH}.