# Merging sorted arrays stored as linked lists

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])
Begin:

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

While(result.size<n):
Minvalue, index = temp.pop()
Value = 0
Value = maxInt
Else :
Return result;

End


• 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)
– ShAr
Commented Sep 30, 2021 at 10:12

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)$$.
• Use a heap instead of an array to store the $k$ smallest elements at every step. Commented Oct 4, 2021 at 21:03