Merge k sorted arrays into one sorted array [duplicate]

Question

I want to write an algorithm of time O(n*lgk) for the merge of k sorted arrays into one sorted array, where n is the total number of elements of all the input arrays.

Could you give me a hint how we could do this?

EDIT: I wrote the following algorithm:

Algorithm(L) // L=[L1, L2, L3, ...., Lk]
  list=LNEW;
  for (i=1; i<=k; i++){
      H[i]=L[i][1];
  }
  BUILD-HEAP(H);
  j=1;
  while (j<n){
         LNEW[j]=H[1];
         yes=0;
         m=1;
         while (m<=k and L[m][j]!=NULL and L[m][j+1]!=NULL and yes!=1){
                if (H[1]==L[m][j]){
                    H[1]=L[m][j+1];
                    yes=1;
                    Heapify(H);
                }
                j=j+1;
  }

Could you tell me if it is right?

Make a heap of the k head elements, then remove the lowest and insert one from the array it originated from. Repeat until all inputs are empty. — Mark Ransom
– Mark Ransom, Commented Jan 19, 2015 at 21:35
Could I just write the steps that are required to be done or should I write a pseudocode? — Mary Star
– Mary Star, Commented Mar 29, 2015 at 22:42

kraskevich · Accepted Answer · 2015-01-19 21:48:28Z

0

We can maintain an array of k elements firstFree, where firstFree[i] is the first unused element in the i-th array. Additionaly, we can have a heap that contains at most k elements(each element is a pair (value, an index of the array that contains this value)). Initially we should put the first elements of all given arrays into this heap. After that, we should repeat the following process until the heap is empty:

Pop the top element of the heap. Add it to the output array.
Increment the firstFree value for the array which contains this element. If it does not exceed this array's size, add the next element to the heap.

This algorithm does n insert and pop operations, so its time complexity is O(n log k).

answered Jan 19, 2015 at 21:48

kraskevich

18.6k4 gold badges37 silver badges46 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Mary Star Over a year ago

So would it be enough to write the steps or would I have to write an algorithm?

Saikat Das Over a year ago

The number of insert and pop operations are in the order of n*k. so complexity of this approach is O(nk log k). geeksforgeeks.org/merge-k-sorted-arrays

Collectives™ on Stack Overflow

Merge k sorted arrays into one sorted array [duplicate]

1 Answer 1

2 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Linked

Related