Ordering k ordered linked lists?

Question

I was reading the solutions here: https://leetcode.com/problems/merge-k-sorted-lists/solution/ on how to union k sorted linked lists into one linked list.

A trivial solution would be to write a function that does the job for 2 linked lists, call it on first 2 lists then call it again with the previous result and the 3rd linked list then again with previous result and 4th linked list and so on.

Another more efficient solution is to do the following:

Pair up k lists and merge each pair.

After the first pairing, k lists are merged into k/2 lists with average 2N/k length, then k/4, k/8 and so on.

Repeat this procedure until we get the final sorted linked list.

My question is: Why the second is more efficient, my mind refuses to accept this fact since I think that we are doing same job in different order. where that improvement came from? what facts did we use to make it faster?

I clarified my question in last comment.

user_9555853 · Answer

Let's say the length of i-th linked list is l[i], the total length of all linked lists is L. Also I assume you (the reader) knows that 2-way merge of two ordered lists has O(a+b) time complexity, where a is the length of the first list and b is the length of the second.

The second solution (solution 2) has a stable time complexity, no matter how the input data is arranged. Content of any linked list was merged log k times before we get the answer, so the total time complexity is O(L log k) in all cases.

Now let's consider the first solution (solution 1). Consider the case that all l[i] are equal (all linked lists are of the same length), the the total time cost T is

T = l[1] * k + l[2] * (k-1) + ... + l[k] * 1
  = l[1] * k(k+1) / 2
  = L * (k+1)/2

Which means the worst case time complexity of solution 1 is O(Lk), which is clearly slower.

A straightforward improvement of solution 1 is merging the lists according to their length, but it does not really help. Sorting lists according to their lengths is not free, and in the case aforementioned, it clearly does not help so the worst case time complexity is not improved.

Solution 2 is better in worst case and also most of cases. Although you can construct a case that solution 1 is quicker, it does not mean solution 1 is better overall.

user_9350720 · Answer

Let the length of the linked lists be [a,b,c,d]. By greedily merging the first two lists, we get:

Pick a and b, we get lengths [a+b,c,d] and total_steps = (a+b).
Pick a+b and c, we get [a+b+c,d] and total_steps = (a+b)+(a+b+c) = 2*a + 2*b + c.
Lastly, we get [a+b+c+d], total_steps = (2*a + 2*b + c) + (a+b+c+d) = 3*a + 3*b + 2*c + d

As you can notice from total_steps, the first two lists (with which you begin merging) have the highest coefficient. If either list has a comparatively large length, then the performance won't be optimal (because of the larger coefficient, as shown). A better approach would be to merge the lists with minimum length at each step (or the k-way merging as listed in your question).

Ordering k ordered linked lists?

2 Answers