## 5 Conclusion and Discussion  
We have proposed two algorithms for solving the suffix sorting problem. The first algorithm runs in \(O(n\log n)\) time and \(O(n)\) space, for both the average case and worst case. Using ideas from Shannon-Fano-Elias codes used in infomation theory, the second algorithm improved the first to an \(O(n)\) worst case time and space complexity. The algorithms proposed perform direct suffix sorting on the input sequence, circumventing the need to first construct the suffix tree.  
We mention that the proposed algorithms are generally independent of the type of alphabet, \(\Sigma\). The only requirement is that \(\Sigma\) be fixed during the run of the algorithm. Any given fixed alphabet can be mapped to a corresponding integer alphabet. Also, since practically the number of unique symbols in \(|T|\) cannot be more than \(n\), the size of \(T\), it is safe to say that \(n\geq|\Sigma|\).  
For practical implementation, one will need to consider the problem of practical code assignment, since the procedure described may involve dealing with very small fractions, depending on \(m\), the block length, and \(|\Sigma|\). This is a standard problem in practical data compression. With \(n\leq 2^{32}\), \(|\Sigma|=256\), we have \(m=32\),and thus we may need to store values as small as \(\frac{1}{|\Sigma|^{32}}=\frac{1}{256^{32}}\) while computing the tags. This translates to \(\frac{1}{256}\), or about \(1.158\times 10^{-77}\). In most implementations, a variable of type double can store values as small as \(1.7\times 10^{-308}\). For the case of 1:2 asymetric partitioning used above, we need only only \(\frac{4n}{9}\) of the \(m\)-blocks, and hence, the overall space needed to store them will still be \(n\) integers, since the size of double is typically twice that of integers. To use the approach for much larger sequences,periodic re-scaling and re-normalization schemes can be used to address the problem. Another approach will be to consider occurrence counts, rather than occurrence probabilities for the \(m\)-blocks. Here, the final number line will be a cummulative count, rather than a cdf, with the total counts being \(n\). Then, the integer code for each \(m\)-block can easily be read off this number line, based on its overall frequency of occurrence. Therefore, we will need space for at most \(\frac{4n}{9}+|\Sigma|\) integers in computing the integer codes for the positions needed. [PERSON] _et al._[35] provide some ideas on how to address practical problems in arithmetic coding.  
Overall, by a careful re-use of previously allocated space, the algorithm requires \((1\frac{2}{3}n\log n-n\log|\Sigma|)\) bits, including the \(n\) bytes needed to store the original string. This translates to \(5\frac{2}{3}n\) bytes, using standard assumptions of 4 byte per integer, and 1 byte for each symbol. This is a significant improvement over the \(10n\) bytes required by the KA algorithm [10], or the \(13n\) bytes required by the KS algorithm [9]. Our algorithm is also unique in its use of Shannon-Fano-Elias codes, traditionally used in source coding, for efficient suffix sorting. This is the first time information-theoretic methods have been used as the basis for solving the suffix sorting problem. We believe that this new idea of using an information theoretic approach to suffix sorting could shed a new light on the problems of suffix array construction, their analysis, and applications.