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?
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.