Merging k sorted linked lists - analysis
- by Kotti
Hi!
I am thinking about different solutions for one problem. Assume we have K sorted linked lists and we are merging them into one. All these lists together have N elements.
The well known solution is to use priority queue and pop / push first elements from every lists and I can understand why it takes O(N log K) time.
But let's take a look at another approach. Suppose we have some MERGE_LISTS(LIST1, LIST2) procedure, that merges two sorted lists and it would take O(T1 + T2) time, where T1 and T2 stand for LIST1 and LIST2 sizes.
What we do now generally means pairing these lists and merging them pair-by-pair (if the number is odd, last list, for example, could be ignored at first steps). This generally means we have to make the following "tree" of merge operations:
N1, N2, N3... stand for LIST1, LIST2, LIST3 sizes
O(N1 + N2) + O(N3 + N4) + O(N5 + N6) + ...
O(N1 + N2 + N3 + N4) + O(N5 + N6 + N7 + N8) + ...
O(N1 + N2 + N3 + N4 + .... + NK)
It looks obvious that there will be log(K) of these rows, each of them implementing O(N) operations, so time for MERGE(LIST1, LIST2, ... , LISTK) operation would actually equal O(N log K).
My friend told me (two days ago) it would take O(K N) time. So, the question is - did I f%ck up somewhere or is he actually wrong about this? And if I am right, why doesn't this 'divide&conquer' approach can't be used instead of priority queue approach?
