Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

The performance of linear time suffix sorting algorithms

Puglisi, S.J., Smyth, W.F. and Turpin, A. (2005) The performance of linear time suffix sorting algorithms. In: Data Compression Conference (DCC) 2005, 29 - 31 March 2005, Snowbird, Utah, USA pp. 358-367.

PDF - Published Version
Download (136kB)
Link to Published Version:
*Subscription may be required


We have illustrated that the superior asymptotic complexity of linear time suffix sorting algorithms does not readily translate into faster suffix sorting, compared to implementations of supralinear algorithms. We have also resolved the ambiguity surrounding the practicality of the Algorithm KA: it is slower than supralinear approaches on real data. We described several optimizations to the O(n) KS algorithm that significantly improve performance for real world inputs, but still fall short of some supralinear approaches. It is worth noting that most of the optimizations we describe could also be applied to Algorithm KB, which may then outperform the well tuned suffix sorter of Manzini and Ferragina (2004).

Item Type: Conference Paper
Item Control Page Item Control Page


Downloads per month over past year