N - Way Merge
Posted on 2001-06-11
I want to merge a set of files efficiently. The files
that I am going to merge are large in size ( > 2 MB) and
are ASCII files.
Now the problem is that I need to develop an algorithm
by which merging takes place efficiently in such a way
that each file is read only once. Once I open a file, it
should be read only once .
I have been suggested to use an n-way merge technique
by which all the files are opened simultaneously, the
first line is read, compared lexicographically and then
written to the new file. Then the second file is read,
and the process is repeated and so on till the end of all
the files are reached.
But this technique seems to take a lot of time. I want
the algorithm to merge and sort with a complexity of o(n).
Can any body suggest me a better technique ?
With some sample code if possible !