Member Avatar for tat2dlady

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

  • 5 Contributors
  • 5 Replies
  • 415 Views
  • 2 Years Discussion Span
  • Latest Post Latest Post by WaltP
Member Avatar for 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 :)

Member Avatar for 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. ;)

Member Avatar for 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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.