Are the parameters (like container size) sensitive to the cache design? They picked 8192 elements by hand-tuning; this is what Judy Arrays tried to accomplish too, and they ran aground on code that got too complicated as it tried to accomodate different architectures.
This is basically Radix sort (radix sort : tries :: heap sort : heaps) with a cache optimization, which is neat.
That was my thought too when I saw the 8192 number, but they deferred with "subject to further research".
I wonder if you could crudely determine a number based on inspecting the size of the cache of the machine at runtime.
I think the most impressive part about the whole thing is that the cache optimization flows naturally out of how the Trie is constructed rather than any voodoo on their part. (Since each string is handled once, rather than m times, where m is the string length, as in a pure radix sort.)
It makes me wonder if the cache optimization aspect was foreseen or accidental.
I haven't looked closely at this 'burstsort', but have read previously about 'cache-oblivious' algorithms, that benefit consistently from memory caches whatever their size. (No tuning for different sizes required.) See discussion here:
See also this lecture on cache oblivious algorithms by Erik Demaine from MIT 6.046 "Introduction to Algorithms" course:
"This is a particularly fun area, one dear to my heart because I've done a lot of research in this area. This is an area co-founded by Professor Leiserson. So, in fact, the first context in which I met Professor Leiserson was him giving a talk about cache oblivious algorithms at WADS '99 in Vancouver I think. Yeah, that has to be an odd year. So, I learned about cache oblivious algorithms then, started working in the area, and it's been a fun place to play. But this topic in some sense was also developed in the context of this class. I think there was one semester, probably also '98-'99 where all of the problem sets were about cache oblivious algorithms."
This is basically Radix sort (radix sort : tries :: heap sort : heaps) with a cache optimization, which is neat.