how would you sort n sorted lists with average length K in O(n*log K) time?

Question

how would you sort n sorted lists with average length K in O(n*log K) time?

Answer 1

You can adapt merge sort to do the job. Merge sort takes advantage of the ease of merging already sorted lists into a new sorted list.

Answer 2

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