I have $k$ sorted arrays stored as linked lists. I need an algorithm to merge them into one single sorted array, also stored as a linked list. How can I do that?

My Code:

Function merge(A[k]) 

// A is array of list to merge.
Array result;
temp //array to save element in each list 
For (i=0:i<k:i++):

 Minvalue, index = temp.pop()
 Value = 0
 If( A[index].head.next==Null):
   Value = maxInt 
 Else :
  A[index].head = A[index].head.next
  Value = A[index].head.key Temp.add(value)
 Return result;

  • $\begingroup$ I would merge each 2 and continue as I'm in an intermediate step of merge sort. If I knew the lengths of the lists in advance, I might think for a while whether to pick longer lists to be merged together or choose one small and one large, or it doesn't matter at all? no of comparisons always O(n log K) $\endgroup$
    – ShAr
    Commented Sep 30, 2021 at 10:12

1 Answer 1


When $k = 2$, you can use the classical merge routine of Merge Sort, which fits the linked list data structure well. In this routine, you repeatedly compare the smallest elements of both arrays, adding the smaller one to the new array, and removing it from its own array.

You can use the same idea for general $k$. Instead of comparing the $k$ smallest elements at every step, you can use a priority queue that stores the smallest elements of each array, thus improving the running time of every step from $\Theta(k)$ to $O(\log k)$.

  • $\begingroup$ Please see my updated question. I think i get the runtime as O(k) and not logk $\endgroup$
    – Redman
    Commented Oct 4, 2021 at 21:01
  • $\begingroup$ Use a heap instead of an array to store the $k$ smallest elements at every step. $\endgroup$ Commented Oct 4, 2021 at 21:03
  • $\begingroup$ yes. First i construct heap temp with first elements of all lists and it has same size of number of lists. Then i pop min value and it’s index in temp heap. Add min value to array A. Then get next value in list 𝐴𝑖𝑛𝑑𝑒𝑥. And add this value to heap temp. And i keep looping for above steps until n. Where am i going wrong? $\endgroup$
    – Redman
    Commented Oct 4, 2021 at 21:53
  • $\begingroup$ Operations on a heap take logarithmic time. $\endgroup$ Commented Oct 4, 2021 at 22:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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