Sorting algorithms which require intermediary steps where two elements are compared can, in the worst case, run no faster than $\Theta(N \log N)$ (i.e. run in $\Omega (N \log N)$).
Suppose it is prophesized the existence of the ultimate comparison sort (TUCS), whose worst case runtime is given by $\mathcal{R}(N)$.
$\mathcal{R}(N) \in \Omega (?)$. What could this be?
$\mathcal{R}(N) \in \mathcal{O}(N \log N)$. The worst is just as poorly as the best-known comparison sort.
Given$1$$9$ identical coins, with $1$ counterfeit coin that weighs more than the rest, how can we identify the counterfeit by using a scale exactly twice.
First, compare weigh coins $123$ and coins $456$. Then we have the following:
$123 > 456$. Then the counterfeit must be among the coins $123$.
$123 = 456$. Then the counterfeit must be among the unweighed coins $789$.
$123 < 456$. Then the counterfeit must be among the coins $456$.
Call the group of coins containing the counterfeit $\mathcal{C}$. Then we can weigh 2 coins in $\mathcal{C}$ for all possible $\mathcal{C}$to produce the following decision tree.
Success! We have found the counterfeit coin in 2 comparisons.
In general, the number of coins can be greater than $9$ coins. Even with $10$ coins, the resulting decision tree has height greater than $2$, so the leaf we would arrive at in $2$ comparisons is counterfeit with only $50 \%$ likelihood (since two scenarios may lead to that same leaf). This is generalized as follows,
$$ \text{Given $K$ comparisons, where each comparison concerns elements} \\ \text{of size $s$, the resulting decision has height $K$ and branch factor $s$.} \\ \text{The number of leaves in this tree is $\mathcal{O} (s^K)$, so the number of } \\ \text{outcomes this tree can decide deterministically is $\mathcal{O}(s^K).$} $$