how would you sort n sorted lists with average length K in O(n*log K) time?
As mentioned in the comments to your question, the O(nlog(k)) is not possible, but here are a couple of algorithms on this page that accomplish your task efficiently; here is one:
Take the first element of each list and create a heap (of size k). Pop the smallest element. Find the array from the element came (let's say it came from list number i). Take the next element from list i and push it in heap. For each element that go in the merged list, we spent log(k) time. So the time complexity is O(N*logk) where N is total number of the elements in all the K lists. -written by: Abhishek Goyal
Take the first element of each list and create a heap (of size k). Pop the smallest element. Find the array from the element came (let's say it came from list number i). Take the next element from list i and push it in heap. For each element that go in the merged list, we spent log(k) time. So the time complexity is O(N*logk) where N is total number of the elements in all the K lists.
-written by: Abhishek Goyal
2.1m questions
2.1m answers
63 comments
56.6k users
