Minimum number of comparisons in comparison-based sorting algorithms
Suppose the input array has $n$ elements. The goal of the sorting algorithm is to compute a permutation of $\{1,2,\ldots,n\}$ - the permutation needed to sort the input.  Let $A$ be the set of these $n!$ permutations.  

Similar to the "guess my number" game (or the game of 20 questions), each comparison can reduce the search space by a factor of at most $2$.  For example, after the first comparison is made, one obtains a partition $A= A_1 \cup A_2$, where $A_1$ is the set of permutations in $A$ that are consistent with the comparison and $A_2$ are the remaining permutations.  The search space for the output is now restricted to $A_1$.  In the worst case, the size of $A_1$ would be larger than that of $A_2$, and so each comparison reduces the size of the search space by a factor of at most $2$. After each comparison is made, the search space is restricted further to those permutations which are consistent with all the comparisons made so far.

Hence, the number of comparisons required to reduce the size of the search space from $n!$ to $1$ is at least $\log_2(n!)$.  The product $1 \times 2 \times \cdots n$ is at least the product of the last $(n/2)$ numbers, which is $(n/2)^{n/2}$, and is at most $n^n$.  Thus, $\log(n!)$ is sandwiched between $(n/2) \log (n/2)$ and $n \log n$, both of which have the same asymptotic growth rate $\Theta(n \log n)$.