Suppose there are $\lceil\log n\rceil$ sorted lists of $\lceil\frac{n}{\log n}\rceil$ elements each. The time complexity of producing a sorted list of all these elements is:  (Hint: Use a heap data structure)$O(n \log \log n)$$(n \log n)$$(n \log n)$$(n^{\frac{3}{2}})$My approach:I know complexity of heap sort is $O(n \log n)$. But little bit confused form where to start.
Merging Sorted lists using Heap Data Structure
algorithms;heaps
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}} &\sim\frac{\sqrt{2\pi n}(n/e)^n}{\sqrt{2\pi n/\log n}^{\log n}(n/e\log n)^n} \\ &\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.