# Given $k$ sorted lists, $O(n \log k)$ complexity, Mergesort rather than Heapsort

I was convinced that my idea for a solution to sort $k$ sorted lists into one list would work with a 'variation' on MergeSort. I was told this would not work and had to use Heapsort, but didn't get any explanation or intuition behind it. (I believe the assumption is that each of the $k$ lists had size $\frac{n}{k}$)

Essentially, my intuition behind using Mergesort was that we have $n$ total elements, but all the steps below height $\log k$ in our recursion tree had already been solved. So at height $\log k$ each list is of size $\frac{n}{k}$, so we perform $\frac{n}{k}$ comparisons and $2\frac{n}{k}$ inserts (to form a new list from the two $\frac{n}{k}$ lists) $k$ times in total, which seems to be on the scale of $O(n)$.

We are now one step up on the recursion tree with $\frac{k}{2}$ lists and we will eventually perform $O(n)$ operations $\log k$ times.

Can anyone provide insight as to why this intuition is wrong? Or if right, how I should go about formally proving it?

• You assume that all of the lists contain the same (or a similar) number of elements. Is this true? If so, I'm inclined to agree with your intuition; the complexity is correct in the extreme cases for $k$, and the reasoning appears sound. – Patrick87 Feb 18 '14 at 20:21
• @Patrick87 yes I believe the assumption was they were all of same size. Thanks for your input. – C.B. Feb 18 '14 at 20:27
• One call of (a generalized) merge is enough; no need to sort recursively at all. Using a heap for computing the next element to pick, this immediately gives you the required runtime; – Raphael Feb 18 '14 at 21:31

I would structure a formal proof of the runtime of your strategy as follows (This is, in structure, very similar to what you already wrote, but does not refer to omitted steps of an imaginary run of Mergesort.):

Arrange the $k$ lists as the leaves of an (almost) complete binary tree. Each internal node of the tree represents the merging of the two lists in its children. Clearly this tree has a height of $\lceil\log k\rceil$.

In this structure, the merges on each level of the tree combined will process each element exactly once.[1] Thus, they take a combined time in $\cal O(n)$. Adding up over all levels of the tree gives a runtime in $\cal O(n\log k)$.

Note that this argument does not require the lists to be of similar size.

Depending on the audience you may be required to elaborate some more on the $\cal O(n)$ bound. This can be done similar to the reasoning in the question:

Merging two lists with size $n_1$ and $n_2$ takes $n_1+n_2$ inserts and (in the worst case) $n_1+n_2-1$ comparisons. Thus, if we perform $i$ merges on a combined total of $n$ elements, they take $n$ inserts and (in the worst case) $n-i$ comparisons.

[1] If $k$ is not a power of $2$, the lowest level processes only a subset of the elements. Obviously the bound still holds for this case.

Like I have solved here, you can mathematical arrive at the solution using recurrence relation alone mere by changing base conditions. Assuming at the bottom all leaves are of the size $$\frac{n}{k}$$,

$$T(n) = T(n/2) + \theta(n); \ n> \frac{n}{k}$$

and, $$T(\frac{n}{k})= \theta(1)$$

By solving above equation we get,

$$T(n)=log_2n+nlog_2k$$