Burstsort is a trie-based string sorting algorithm that distributes strings into small buckets whose contents are then sorted
in cache. This approach has earlier been demonstrated to be efficient on modern cache-based processors [Sinha & Zobel, JEA
2004]. In this paper, we introduce improvements that reduce by a significant margin the memory requirements of burstsort.
Excess memory has been reduced by an order of magnitude so that it is now less than 1% greater than an in-place algorithm.
These techniques can be applied to existing variants of burstsort, as well as other string algorithms.
We redesigned the buckets, introducing sub-buckets and an index structure for them, which resulted in an order-of-magnitude
space reduction. We also show the practicality of moving some fields from the trie nodes to the insertion point (for the next
string pointer) in the bucket; this technique reduces memory usage of the trie nodes by one-third. Significantly, the overall
impact on the speed of burstsort by combining these memory usage improvements is not unfavourable on real-world string collections.
In addition, during the bucket-sorting phase, the string suffixes are copied to a small buffer to improve their spatial locality,
lowering the running time of burstsort by up to 30%.