balanced k-way sort-merge

[tat2dlady]

Does anyone know basic pseudocode for a balanced k-way sort-merge? Thanks for any info you may have.

[marinme]

Does anyone know basic pseudocode for a balanced k-way sort-merge? Thanks for any info you may have.

I'm not sure what you mean by k-way, but if you define it a little better, we may be able to help :)

[Narue]

>I'm not sure what you mean by k-way
Instead of just taking one stream of data, then dividing and sorting it recursively, a k-way sort divides the initial stream into k smaller streams and sorts each of them individually. By "balanced", it means that the value of k is consistent from input through output.

And no, I don't have pseudocode for it, nor do I have real code that's not under a non-disclosure agreement. And I'm too lazy to come up with something new. ;)

[tat2dlady]

It is a 5-way balanced sort-merge. I have 10 temp files to work with (5 for input and 5 for output). I have to use a clump size of 1,000, write clumps of 1,000 records to the first 5 files. Then, I get 1 clump from each of those files and write the clumps to the alternating other 5 files. An example:

I have 1,000,000 records.

After phase 1:
Each of Files 1 - 5 have 200 clumps of 1,000 that are sorted.

In phase 2:
The first pass should put 40 clumps of 5,000 records in files 6 - 10.
The second pass should put 8 clumps of 25,000 records in files 1 - 5.
etc...

I am having a hard time controlling the loop to do the writing to the alternate files. Thanks if you have any input about it.

[Randgalt]

I have an implementation here: http://sourceforge.net/projects/kwaymerge

[WaltP]

I have an implementation here: http://sourceforge.net/projects/kwaymerge

I'm sure after 2 1/2 years the OP will be ecstatic to hear that. :icon_rolleyes: