1
$\begingroup$

Ok, so there's this classical problem of "merging k sorted arrays into one long sorted array using merge() from mergesort". There are many articles and videos about this in internet, which all lead to the "keep merging arrays 2 on 2 until you have just one. This takes O(nk log k) time.". I understand this explanation for this algorithm and this time complexity.

But what if the sorted arrays have sizes $$1, 2, 4, 8, 16, ..., 2^{k}$$ ? and we consider $n$ now being the final array length, i. e., $$ n = 1 + 2 + 4 + ... + 2^{k} = 2^{k+1} - 1 $$ Would it be possible to merge them all into a single array in better time?

Also, could you evaluate my pseudocode for this algorithm:

(Consider A as being all those arrays concatenated, and indexing beggining on 1, and merge() as being mergesort's merge(array, first index of first array being merged, last index of first array being merged, last index of last array being merged)):

for(m = 1; m <= lg(n+1)/2; m++){
  for(i = 1; i < k/2; i = 4*i){
    merge(A, i, i*2^(m) -1, i*4^(m) -1);
  }
}

(I know it looks confusing, that's why I am asking here too. I am sorry if my question is being too loose, but any help will be welcome!)

(I am also aware the min heaps implementations, but I need to know about this method using mergesort's merge()!)

(Thank you for reading until here!)

$\endgroup$
2
$\begingroup$

You should use something like a Huffman Coding approach where the leaves are the sizes of the arrays. Merge the arrays from leaves to the root and you'll get a local-optimum at least. I don't have a proof that this is the most optimal solution yet.

| cite | improve this answer | |
$\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.