# Lower bound for merging $m$ sorted arrays (decision tree leaves count - permutations)

I need some help understanding how to calculate the lower bound on the time complexity of merging $$m$$ sorted arrays of length $$n$$.

The bound should be $$nm \lg(m)$$. I need to prove this using a decision tree.

I tried counting the number of possible permutations (which would be the number of leaves in the tree) but I got stuck. I tried the following:

When merging the 2nd array with the first, we have $$\binom{2n}{n}$$ possibilities to place the elements. When merging the 3rd, we have $$\binom{3n}{n}$$ and so on, so the total number of permutations is:

$$\binom{2n}{n} \binom{3n}{n} \dots \binom{mn}{n}$$

The height of the tree is denoted $$h$$.

$$h > \lg{\binom{2n}{n} \binom{3n}{n} \dots \binom{mn}{n}}$$

And from here I don't know how to prove the complexity.

My question is - did I count the permutations correctly? Is there a more simple bound? How to continue from here?

Also, ould this problem possibly be equivalent to the problem of sorting an $$m$$-sorted array of size $$nm$$? Because in this problem it is easy to prove that the bound is $$nm \lg(m)$$.

• The bound for unsorted arrays is $nm \lg (nm)$, not $nm \lg (m)$. Otherwise let $m = 1$ and voila we have linear time sorting.
– orlp
Aug 10, 2019 at 10:58
• You're right, I meant k-sorted with $k=m$. Edited. Aug 10, 2019 at 11:06

Stirling's formula shows that $$\binom{N}{pN} \sim \frac{2^{H(p)N}}{\sqrt{2\pi p(1-p)N}},$$ where $$H(p)$$ is the binary entropy function: $$H(p) = p\log \frac{1}{p} + (1-p) \log \frac{1}{1-p}.$$ In particular, this shows that for $$k \geq 2$$, $$\binom{kn}{n} = (1+o(1)) \frac{2^{H(1/k)kn}}{\sqrt{2\pi(1/k)(1-1/k)kn}} \geq (1+o(1)) \frac{2^{n\log k}}{\sqrt{2\pi n}}.$$ Therefore $$\log \binom{kn}{n} \geq n\log k - O(\log n),$$ where the big O doesn't depend on $$k$$. Summing this for $$k=2,\ldots,m$$, we deduce $$h \geq n \log m! - O(m\log n) \geq nm \log m - O(nm),$$ using Stirling's formula again.