Merging Sorted lists using Heap Data Structure

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)

1. $O(n \log \log n)$

2. $θ(n \log n)$

3. $Ω(n \log n)$

4. $Ω(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.

• A heap data structure can be used for heap sort, but it is actually a priority queue. You insert elements into the heap, and then you can extract them in order of "priority". For example, a max-heap would return the largest element first and a min-heap would return the smallest element first. As an additional hint, you're given a bunch of already-sorted lists. What sort algorithm would you consider first? Feb 5, 2015 at 22:14

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.
• Just as a comment, the $\Omega(n \log \log n)$ lower bound does assume that all of the elements are distinct. Feb 6, 2015 at 0:21
• @YuvalFilmus How do you come up with $\frac{n!}{(n/\log n)!^{\log n}}$. Could you please elaborate. Feb 6, 2015 at 10:00
• Divide $\{1,\ldots,n\}$ into $\log n$ equal parts $B_1,\ldots,b_{\log n}$. This is the number of permutations of $\{1,\ldots,n\}$ in which the elements of each $B_i$ appear in order. Feb 6, 2015 at 14:03