Merging a bunch of tables: Algorithm suggestions?

[Bitweasil]

Merging big tables sucks.

Or something like that.

My table merge code currently works as follows:

- Load up a whole bunch of sorted partial tables
- Memory map them (64-bit OS required, not even screwing with 32-bit boxes here)
- Go through the "top" element of each list, grab the minimum, stick it in the output stream.

This is a really bad algorithm, as it scales with O(L*N) where L is the length and N is the number of table parts being merged. Merging a lot of tables sucks.

Anyway, suggestions on a better way to do this?

[Sc00bz]

I wrote one that uses a priority queue and does it in O(L*log(N)) operations. It's http://www.freerainbowtables.com/phpBB3 ... &f=2#p7216 "rtperfecter"

[Bitweasil]

Great, thanks! I'll take a look at that. I'm weak on my sort/merge algorithms.