Prove that $n! ≥ (⌈n/2⌉)^{⌈n/2⌉}$

Question

Prove that : $n! ≥ (⌈n/2⌉)^{⌈n/2⌉}$

Context

This is necessary for the proof that comparison-based sorting has a lower bound of $\mathcal{O}(n \cdot \log n)$

The proof goes like this:

1. There are $n!$ ways to permutate a sequence.
2. Comparison-based sorting needs to be able to distinguish all of those and it can only compare two elements at a time.
3. A binary tree on $n!$ elements has a depth of $\log(n!)$, hence comparison-based sorting has a lower computational complexity bound of $\mathcal{O}(n!)$

Now the question is if the following is true: $\mathcal{O}(n \cdot \log n) = \mathcal{O}(n!)$

If the inequality from above is true, then $\mathcal{O}(n \cdot \log n) \subseteq \mathcal{O}(n!)$ is true. As there are algorithms like Mergesort, we know that the other direction is true.

Answer 1

Hint: $2a*(2a-1)*(2a-2)*...*a*k > a^a$ where $k>0$.

Answer 2

$$n! \geq n(n-1)(n-2)(n-3) \cdots \lceil n/2 \rceil \geq (\lceil n/2 \rceil)^{\lceil n/2 \rceil}$$