CODEWITHSUNDEEP
algorithmmergesort
rena-c
rena-c

Reputation: 325

Merging unknown number of arrays

My problem is,is it possible to merge (unknown number of arrays) into a one array.so i dont know the number of arrays exactly(not like merging two array merging n array etc.) signature:

  > int [] merge(int k)//k is number of arrays to be merged into a one
    > merge them 
     //and so on..
    > 
    > return array;

Upvotes: 0

Views: 431

Answers (4)

amit
amit

Reputation: 178481

Though it is possible to iteratively merge arrays, a more efficient way will be a k-way merge, which is done in O(nlogk) where k is the number of arrays and n is the total number of elements, using a priority queue.

Note: It cannot be done better then O(nlogk), because if it was possible [let's say with complexity O(g(n)) where g(n) is as asymptotically weaker then nlogn] - then we can produce the following sorting algorith:

sort(array A):
  split A into n arrays, each of size 1, B1,...,Bn
  A <- special_merge(B1,...Bn)
  return A

It is easy to see that this algorithm is of complexity O(g(n) + n) = O(g(n)), and we get a contraditcion, since we got a sort better then O(nlogn) - which is not possible with compartions based algorithms, since this problem is Omega(nlogn)

Upvotes: 4

Rafał Dowgird
Rafał Dowgird

Reputation: 45131

Yes, it is possible and for k arrays it's usually done using a priority queue of size k. The queue holds one element from each array (together with a tag for remembering which array the element came from.)

Initially the queue is filled with the minimal element from each array. Then you just iteratively remove the minimal element from the queue, and add next element to the queue, from the array the last minimal element came from.

Assuming the standard heap implementation of the pqueue, this yields O(nlog(k)) complexity.

Upvotes: 0

High Performance Mark
High Performance Mark

Reputation: 78344

Sure, merge array 1 with array 2, merge array 1+2 with array 3, merge array 1+2+3 with array 4, continute until you have no arrays left. All you need is a method to merge 2 arrays, and a method to call this with a list of arrays until the list is empty.

Upvotes: 1

mrk
mrk

Reputation: 3191

If you know how to merge 2 arrays, then you can merge any number of arrays ;)

Upvotes: 3

Related Questions