TITLE: $O(n \log k)$ for merging of $k$ lists with total of $n$ elements
QUESTION [0 upvotes]: Is it possible to merge $K$ sorted list into one sorted list where n is the total number of elements in all the input lists in $O(n \log k)$ time?
What I tried to do is, taking the list, and adding all the first elements of all the list to an array of size $k$ then find the smallest data among the elements and then add the second data from the list whose respective first element is the smallest element that was present in the array. Replace the first element by the second element. then the loop would go $n$ times, every time one smallest element is selected. Now what I want to do is that to find the smallest element in array $k$ in $\log k$ times. Is that possible??

REPLY [2 votes]: Assuming lists as your container types, merging two sorted lists in-place of sizes $n_1,n_2$ takes $O(n_1+n_2)$ steps (if yo use arrays, the complexity is the same, but you'd use a separate "output" array). Hence you can essentially half the number of lists by merging them in pairs in $O(n_1+n_2+\ldots+n_k)=O(n)$ steps. If $k\le 2^r$, we can reach a single sorted list in at most $r$ rounds, i.e. the run time is $O(nr)=O(n\log k)$.
{"set_name": "stack_exchange", "score": 0, "question_id": 881599}