0
$\begingroup$

In trying to write pseudocode for it, this is my attempt:

I'm just trying to write a pseudo-code for it and explain the run time.

So far this is what I have:

k-merge-sort(L) 
  { if length(L1) <2 return L1 
   else 
     { split L into L1, L2, L3 
     A1 = k-merge-sort(L1) 
     A2 = k-merge-sort(L2) 
     .... 
     An = k-merge-sort(Ln) 
     Bn = k-merge(A1..An) 
     } 

Thoughts? Thank you! As for the run time, the logn part of it comes for it being a complete binary tree's height, the height being the number of lists and the n*k part from the items.

$\endgroup$
1
$\begingroup$

This is classic multi-way merge: Create a heap of pairs (element, which list did it come from). Initialize with first elements of each list. Repeatedly remove the minimum element and add the next element from its originating list.

Also discussed before at https://stackoverflow.com/questions/5055909/algorithm-for-n-way-merge .

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.