There are short and sweet proofs of various forms of Stirling's approximation. But even the sweetest among them don't instill the same conviction in the reader as a direct bijective proof.
Computer scientists can often get away with a very weak form of Stirling's approximation:
$$(n/2)^{n/2} \leq n! \leq n^n$$
From this follows
$$(n/2)\ log(n) - (n/2)\ log(2) \leq log(n!) \leq n\ log(n)$$
and therefore $log(n!) = \Theta(n\ log(n))$. This is sufficient to establish the lower bound on comparison-based sorting algorithms and many other asymptotic bounds.
Does anyone know a natural bijective proof of $(n/2)^{n/2} \leq n! \leq n^n$?