Merging Sorted lists using Heap Data Structure
Hint: Try to merge the lists in the correct way, using the fact that merging lists of size $m_1,m_2$ costs $O(m_1+m_2)$. If you do this correctly, you will obtain an $O(n\log\log n)$ algorithm.

We can also get a matching lower bound. The number of possible answers is
$$
\begin{align*}
\frac{n!}{(n/\log n)!^{\log n}} &amp;\sim
\frac{\sqrt{2\pi n}(n/e)^n}{\sqrt{2\pi n/\log n}^{\log n}(n/e\log n)^n} \\ &amp;\sim
\frac{(\log n)^{\log n}}{\sqrt{2\pi n}^{\log n-1}}(\log n)^n.
\end{align*}
$$
The dominant term here is $(\log n)^n = \exp(n\log\log n)$, and we get an $\Omega(n\log\log n)$ lower bound in the decision tree model.