## 4 Algorithm II: Improved Algorithm
### Improved Sorting - Using Shannon-Fano-Elias Codes  
The key to improved sorting is to reduce the number of bucket sorts in the above procedure. We do this by pre-computing some information before hand, so that the sorting can be performed based on a small block of symbols, rather than one symbol at a time. Let \(m\) be the block size. With the precomputed information, we can perform a comparison involving an \(m\)-block symbol in \(O(1)\) time. This will reduce the number of bucket sorts required at each level \(h\) from \(\alpha^{h-1}\) to \(\frac{\alpha^{h-1}}{m}\), each involving \(\alpha^{h_{max}-h}\) symbols. By an appropriate choice of \(m\), we can reduce the complexity of the overall sorting procedure. For instance, with \(m=\log\log n\), this will lead to an overall worst case complexity in \(O(\frac{n\log n}{\log\log n})\) time for determining the suffix array of \(T_{1}\) from that of \(T_{2}\). With \(m=\log n\), this gives \(O(n)\) time. We use \(m=\log n\) in subsequent discussions. The question that remains then is _how_ to perform the required computations, such that _all_ the needed block values can be obtained in linear time. Essentially, we need a pair-wise global partial ordering of the suffixes involved in each recursive step. First, we observe that we only need to consider the ordering between pairs of suffixes at the same level of recursion. The relative order between suffixes at different levels is not needed. For instance, using the example sequence of Figure 3, the sets of suffixes for which we need the pair-wise orderings will be those at positions: \(\{\{1,5,10,14\};\{2,8\};\{4,13\}\}\). Each subset corresponds to a level of recursion, from \(h=2\) to \(h=h_{max}-1\). Notice that we don't necessarily need those at level \(h=1\), as we can directly induce the sorted order for these suffixes from \(SA_{2}\), after sorting \(T_{2}\). We need a procedure to return the relative order between each pair of suffix positions in constant time. Given that we already have an ordering from the right tree in \(SA_{2}\), we only need to consider the prefixes of the suffixes in the left tree up to the corresponding positions in \(T_{2}\), such that we can use entries in \(SA_{2}\) to break the tie, after a possible \(\frac{\alpha^{h-1}}{m}\) bucket sorts. Let \(Q_{i}\) be the \(m\)-length prefix of the suffix \(T^{\prime}_{i}\): \(Q_{i}=T[i\ldots i+m-1]\). We can use a simple hash function to compute a representative of \(Q_{i}\), for instance using the polynomial hash function:  
\[h(Q_{i})=\sum_{j=0}^{m-1}|\Sigma|^{m-1}f(Q_{i}[j])\mod n^{\prime}\]  
where \(f(x)=k\), if \(x\) is the \(k\)-th symbol in \(\Sigma,k=0,1,\ldots,|\Sigma|-1\), and \(n^{\prime}\) is the nearest prime number \(\geq n\). The problem is that the ordering information is lost in the modulus operation. Although order-preserving hash functions exist (see [31]), these run in \(O(n)\) time on average, without much guarantees on their worst case. Also, with the \(m\)-length blocks, this may require \(O(mn)=O(n\log n)\) time on average. We use an information theoretic approach to determine the ordering for the pairs. We consider the required representation for each \(m\)-length block as a codeword that can be used to represent the block. The codewords are constrained to be order preserving: That is, \(\mathcal{C}(Q_{i})<\mathcal{C}(Q_{j})\) iff \(Q_{i}\prec Q_{j}\) and \(\mathcal{C}(Q_{i})=\mathcal{C}(Q_{j})\) iff \(Q_{i}=Q_{j}\), where \(\mathcal{C}(x)\) is the codeword for sequence \(x\). Unlike in traditional source coding where we are given _one_ long sequence to produce its compact representation, here, we have a set of short sequences, and we need to produce their respective compact representations, and these representations must be order preserving. Let \(P_{i}\) be the probability of \(Q_{i}\), the \(m\)-length block starting at position \(i\) in \(T\). Let \(p_{i}\) be the probability of symbol \(t_{i}=T[i]\).