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

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 :)

>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. ;)

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.

This article has been dead for over six months. Start a new discussion instead.