## 4 Algorithm II: Improved Algorithm
### Improved Sorting - Using Shannon-Fano-Elias Codes
Thus, the running time for the algorithm is given by the solution to the recurrence : \(\varphi(n)=\varphi(\lceil\frac{2}{3}n\rceil)+O(n)\). This gives \(\varphi(n)=O(n)\). Combined with Theorem 2, this establishes the linear time bound for the overall algorithm. We improve the space requirement using an alternative merging procedure. Since we now have \(SA_{1}\) and \(SA_{2}\), we can modify the merging step by exploiting the fact that any conflict that can arise during the merging can be resolved by using only \(SA_{2}\). To resolve a conflict between suffix \(T_{1_{i}}\) in \(T_{1}\) and suffix \(T_{2_{j}}\) in \(T_{2}\), we need to consider two cases:  
* Case 1: If \(j\mbox{ mod }3=1\), we compare \(\langle T_{1}[i],SA_{2}[SA_{2}^{\prime}[i+1]]\rangle\) versus \(\langle T_{2}[j],SA_{2}[SA_{2}^{\prime}[j+1]]\rangle\), since the relative order of both \(T_{1_{i+1}}\) and \(T_{2_{j+1}}\) are available from \(SA_{2}\). * Case 2: If \(j\mbox{ mod }3=2\), we compare \(\langle T_{1}[i],T_{1}[i+1],SA_{2}[SA_{2}^{\prime}[i+2]]\rangle\) versus \(\langle T_{2}[j],T_{2}[j+1],SA_{2}[SA_{2}^{\prime}[j+1]]\rangle\). Again, for this case, the tie is broken using the triplet, since the relative order of both \(T_{1_{i+2}}\) and \(T_{2_{j+2}}\) are also available from \(SA_{2}\). Consider the step just before we obtain \(SA_{1}\) from \(SA_{2}\) as needed to obtain the final \(SA\). We needed the codes for the \(m\)-blocks in sorting to obtain \(SA_{2}\). Given the 1:2 non-symetric partitioning used, at this point, the number of such \(m\)-blocks needed for the algorithm will be \(\frac{2}{3}\cdot\frac{2}{3}n\). These require \(\frac{4}{9}n\) integers to store. We need \(\frac{2}{3}n\) integers to store \(SA_{2}\). At this point, we also still have the inverse SA used to merge the left and right suffix arrays to form \(SA_{2}\). This requires \(\frac{4}{9}n\) integers for storage. Thus, the overall space needed at this point will be \(1\frac{5}{9}n\) integers, in addition to the space for \(T\). However, after getting \(SA_{2}\), we no longer need the integer codes for the \(m\)-length blocks. Also, the merging does not involve \(SA_{1}^{{}^{\prime}}\), so this need not be computed. Thus, we compute \(SA_{2}^{\prime}\), and re-use the space for the \(m\)-block codes. \(SA_{2}^{\prime}\) requires \(\frac{2}{3}n\) integers. Further, since we are merging \(SA_{1}\) and \(SA_{2}\) from the same direction, we can construct the final SA in-place, by re-using part of the space used for the already merged sections of \(SA_{1}\) and \(SA_{2}\). (See for example [33, 34]). Thus, the overall space requirement in bits will be \((n\log|\Sigma|+n\log n+\frac{2}{3}n\log n)=(n\log|\Sigma|+1\frac{2}{3}n\log n)\), where we need \(n\log|\Sigma|\) bits to store \(T\), \(n\log n\) bits for the output suffix array, and \(\frac{2}{3}n\log n\) bits for \(SA_{2}^{{}^{\prime}}\). \(\square\)  
The above translates to a total space requirement of \(7\frac{2}{3}n\) bytes, using standard assumptions of 4 bytes per integer, and 1 byte per symbol. Though the space above is \(O(n)\), the \(\frac{2}{3}n\log n\) bits used to store \(SA_{2}^{{}^{\prime}}\) could further be reduced. We do this by by making some observations in the above two cases encountered during merging. We can notice that after obtaining \(SA_{2}\) and \(SA_{1}\), we do not really need to store the text \(T\) anymore. The key observation is that, merging of \(SA_{2}\) and \(SA_{1}\) proceeds in the same direction for each array, for instance, from the least to the largest suffix. Thus, at the \(k\)-th step, the symbol at position \(i=SA_{2}^{{}^{\prime}}[k]\) (that is, \(T_{2}[i]\)) can easily be obtained using \(SA_{2}\), and two \(O(|\Sigma|)\) arrays, namely, \(B_{1}\): which stores the symbols in \(\Sigma\) in lexicographic order, and \(B_{2}\) that stores the cummulative count for each symbol in \(T_{2}\). For \(T_{2}[i+1]\), we compute \(SA_{2}[SA_{2}^{{}^{\prime}}[i]+1]\)) and use the value as index into \(B_{2}\).