Q:

Algorithm for N-way merge

A 2-way merge is widely studied as a part of Mergesort algorithm.
But I am interested to find out the best way one can perform an N-way merge?
Lets say, I have N files which have sorted 1 million integers each.
I have to merge them into 1 single file which will have those 100 million sorted integers.
Please keep in mind that use case for this problem is actually external sorting which is disk based. Therefore, in real scenarios there would be memory limitation as well. So a naive approach of merging 2 files at a time (99 times) won't work. Lets say we have only a small sliding window of memory available for each array.
I am not sure if there is already a standardized solution to this N-way merge. (Googling didn't tell me much).
But if you know if a good n-way merge algorithm, please post algo/link.
Time complexity: If we greatly increase the number of files (N) to be merged, how would that affect the time complexity of your algorithm?
Thanks for your answers.
I haven't been asked this anywhere, but I felt this could be an interesting interview question. Therefore tagged.

A:

How about the following idea:

Create a priority queue
Iterate through each file f

enqueue the pair (nextNumberIn(f), f) using the first value as priority key

While queue not empty

dequeue head (m, f) of queue
output m
if f not depleted

enqueue (nextNumberIn(f), f)

Since adding elements to a priority queue can be done in logarithmic time, item 2 is O(N × log N). Since (almost all) iterations of the while loop adds an element, the whole while-loop is O(M × log N) where M is the total number of numbers to sort.
Assuming all files have a non-empty sequence of numbers, we have M > N and thus the whole algorithm should be O(M × log N).

A:

Search for "Polyphase merge", check out classics - Donald Knuth & E.H.Friend.
Also, you may want to take a look at the proposed Smart Block Merging by Seyedafsari & Hasanzadeh, that, similarly to earlier suggestions, uses priority queues.
Another interesting reasonsing is In Place Merging Algorithm by Kim & Kutzner.
I also recommend this paper by Vitter: External memory algorithms and data structures: dealing with massive data.

A:

One simple idea is to keep a priority queue of the ranges to merge, stored in such a way that the range with the smallest first element is removed first from the queue.  You can then do an N-way merge as follows:

Insert all of the ranges into the priority queue, excluding empty ranges.
While the priority queue is not empty:

Dequeue the smallest element from the queue.
Append the first element of this range to the output sequence.
If it's nonempty, insert the rest of the sequence back into the priority queue.

The correctness of this algorithm is essentially a generalization of the proof that a 2-way merge works correctly - if you always add the smallest element from any range, and all the ranges are sorted, you end up with the sequence as a whole sorted.
The runtime complexity of this algorithm can be found as follows.  Let M be the total number of elements in all the sequences.  If we use a binary heap, then we do at most O(M) insertions and O(M) deletions from the priority queue, since for each element written to the output sequence there's a dequeue to pull out the smallest sequence, followed by an enqueue to put the rest of the sequence back into the queue.  Each of these steps takes O(lg N) operations, because insertion or deletion from a binary heap with N elements in it takes O(lg N) time.  This gives a net runtime of O(M lg N), which grows less than linearly with the number of input sequences.
There may be a way to get this even faster, but this seems like a pretty good solution.  The memory usage is O(N) because we need O(N) overhead for the binary heap.  If we implement the binary heap by storing pointers to the sequences rather than the sequences themselves, this shouldn't be too much of a problem unless you have a truly ridiculous number of sequences to merge.  In that case, just merge them in groups that do fit into memory, then merge all the results.
Hope this helps!

