0
$\begingroup$

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??

$\endgroup$
2
$\begingroup$

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)$.

$\endgroup$
1
  • $\begingroup$ does it mean you need to use recursion in order to merge the sublists in pairs? because it seems that you merged them consecutively (the first two sublists, and then that new sublist with the 3rd sublist, and so on...) $\endgroup$
    – gbi1977
    Dec 2 '17 at 21:26
1
$\begingroup$

What you want to do is to keep k pointers, one for each list. Now maintain a min-heap with the elements here. The min-heap will always have k elements. When the min comes to be from list i, increment the ith pointer by 1 and add the new element from list i into the min-heap. As element addition and min extraction for min heap of size k can be done in O(log k) time and constant time respectively, you get the total bound of O(n log k).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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