Burstsort Library

Motivation

I wanted the fastest algorithm to sort strings for my program, and after a search of the scientific journals I decided on Burstsort and its variants. There was, however, no implementation of Burstsort free available so I wrote my own.

Description

Burstsort is currently the fastest algorithm for sorting strings on cache-architectures.

News for version 2.0

• The second release improves greatly on the original. There are no memory leaks, the code is easier to read, only uses the C++ standard library instead of the C standard library, and it is even faster! Variable alphabets are now provided, and I will add support for orthographic sorting in the next version.

News for version 1.0

• This is the first release. It works, but there are some limitations. Currently, only strings containing the 26 lowercase Latin characters are accepted by the Bursttrie. In the next version variable alphabets will be supported. The memory allocation strategy for the trie may be inefficient. I have not yet compared my implementation with the results presented in the papers on Burstsort.

Downloads

Use the project page at sourceforge: http://www.sourceforge.net/projects/burstsort

License

Burstsort is licenced under the GPL, not the LGPL.

Stefan Webb