title: Algorithm for N-way merge
body: <p>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?</p>
  
  <p>Lets say, I have <code>N</code> 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.</p>
  
  <p>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.</p>
  
  <p>I am not sure if there is already a standardized solution to this N-way merge. <em>(Googling didn't tell me much)</em>.</p>
  
  <p>But if you know if a good n-way merge algorithm, please post algo/link.</p>
  
  <p><strong>Time complexity:</strong> If we greatly increase the number of files (<code>N</code>) to be merged, how would that affect the time complexity of your algorithm?</p>
  
  <p>Thanks for your answers.</p>
  
  <p><em>I haven't been asked this anywhere, but I felt this could be an interesting interview question. Therefore tagged.</em></p>