# How many comparisons in the worst case, does it take to merge 3 sorted lists of size n/3?

How many comparisons in the worst case, does it take to merge 3 sorted lists of size n/3? (where n is a power of 3)

I was told it takes:

$$2(n-2) + 1 = 2n-3$$

However, I can't seem to figure out why.

The way to merge them I was thinking just to merge two of the lists, and then merge that big 2/3 list with the remaining list. How come the worst case of that 2n-3?

The complete explanation I was given was:

The worst case occurs if the first list empties when there is exactly 1 item in each of the other two. Prior to this, each of the other n−2 numbers requires 2 comparisons before going into the big list. After this, we only need 1 more comparison between the 2 leftover items.

Which doesn't make complete sense to me. Not sure if its just the grammar of the sentences, but not sure where the $2(n-2)$ came from... What does:

The worst case occurs if the first list empties when there is exactly 1 item in each of the other two.

even mean?

When it says "prior to this", its not clear to me what exactly happened before hand...

What does the "big list" referring to? How did we even get a "big list"?

Btw, I am not looking for an asymptotic answer.

I was also interested in the generalization of my question though:

Extending my question, if we extend merge sort algorithm but instead of 2, to divide by some constant c, why would the recurrence be of the form:

$$T(n) = cT \left( \frac{n}{c} \right) + \left[ (c-1)(n-(c-1)) + \sum^{c-2}_{i=1} i\right]$$

The extra term for merging is not entirely clear to me.

First of all, we have to distinguish between two different questions. The first is about analyzing the specific (generalized) merging algorithm used in merge sort. The second is about analyzing the problem.

Merge sort merging

The paragraph you quote attempts to analyze the merge sort merging algorithm. It only gives a lower bound on the number of comparisons, though presumably it is easy to show that it is also an upper bound. In order to give a lower bound of $C$ on the number of comparisons, it is enough to describe a situation in which the algorithm uses $C$ comparisons. Such a situation is the "worst case [instance]" that the paragraph is talking about.

The merging algorithm starts with three lists of length $n/3$, and constructs a "big list" of length $3$. The algorithm works by comparing the smallest elements in all remaining lists, and moving the smallest one to the top of the big list. As the algorithm progresses, eventually lists will empty — all their elements have been moved to the big list.

The paragraph suggests to consider the situation in which the first list empties when the other two have exactly one element remaining, which it claims is a "bad case", indeed the "worst case"; for the sake of the lower bound, we don't care whether this is actually true. You have to argue that the situation can actually happen, and carefully count all comparisons done by the merging algorithm. The merging algorithm the paragraph considers always compares the bottom elements of all remaining lists, requiring $\ell-1$ comparisons if $\ell$ non-empty lists remain. In this case, as long as all lists are non-empty, we need two comparisons per element.

At the situation considered there are only two elements left, so $n-2$ elements have been processed with two comparisons per element, leading to $2(n-2)$ comparisons. The final two elements require one more comparison. It is not too hard to check that this is indeed the worst case: this situation maximized the number of times that an element requires two comparisons to process.

The more general case with $c$ lists is very similar. Again the worst case is when the first list empties when all other lists have exactly one element. Up to now there have been $(c-1)(n-c+1)$ comparisons. The next element will require $c-2$ comparisons only (since there are only $c-1$ non-empty lists), the element after that $c-3$, and so on. This gives the formula you state.

General question

A different question one can ask is: given $c$ sorted lists of length $n/c$, how many comparisons are needed to determine the sorted order of all of them merged. There are two variants of this question:

1. What is the minimal $C$ such that there is an algorithm which outputs the correct order and never uses more than $C$ comparisons; the algorithm is only allowed to access the lists by comparing two elements. This is the so-called decision-tree model.

2. What is the minimal running time of an algorithm merging the lists.

These questions are rather different. The first question is much easier to answer, and I will only comment on it. However, the minimal $C$ doesn't necessarily correspond to an efficient algorithm, since determining which comparison to do next could be difficult.

The classical lower bound on sorting extends to this situation. Given $c$ sorted lists of length $n/c$, the number of possible ways they fit together to one big list is $\frac{n!}{(n/c)!^c} = \Theta\big(\frac{c^n}{n^{(c-1)/2}}\big)$, and we obtain a lower bound of $(\log_2 c)n - O_c(\log n)$. Fredman's classical result shows that there is a corresponding algorithm in the decision-tree model using at most $(2+\log_2 c)n$ comparisons (for large enough $n$, depending on $c$), which is better than the merge sort merging procedure for $c \geq 5$. The correct answer is probably $(\log_2 c)n \pm o_c(n)$. Indeed, using heaps you can merge $c$ lists with $O((\log c)n)$ comparisons efficiently, as described for example in answers to the following question.

I think the worst case is actually better; about (5/3)n instead of 2n.

We start with three lists of length n/3, a total of n elements. We repeatedly determine the smallest element, and move it from its list to the output list.

As long as we have three non-empty lists, this is done easily with two comparisons: We compare the smallest elements of list 1 and list 2, then compare the smaller one with the smallest element of list 3. At some point we are down to two lists, so we need one comparison for the next element (save one comparison) until we are down to one list, where we need no comparisons (save two comparisons per element). Worst case we go from three lists with one element each to two lists then to one list, and save 3 comparisons, which gives us 2n-3 comparisons.

However, there are two situations now: If the element of list 3 is the smallest, then we still know whether the element of list 1 or list 2 was smaller after the move, so we save a comparison. If the element of list 3 is not the smallest the list 3 doesn't empty, so there will be elements left in list 3 when one of the other lists empties.

Assume the element of list 3 was the smallest (k) times until one list was empty. We saved k comparisons. If k < n/3 then there are n/3 - k items left in list 3, and at least one more element in another list. Worst case we save one comparison (n/3 - k) times, then we have one item left and save another two comparisons. So n/3 + 2 comparisons are saved in total, which means we need 5/3 n - 2 comparisons.

PS. Yuval Filmus states a lower bound of about $$n log_2(3)$$ which is about 1.585n, so 5/3 n - 2 ≈ 1.667 n isn't bad.