From Nielsen & Chuang (page 138):
Suppose an $n$ element list is sorted by applying some sequence of compare-and-swap operations to the list. There are $n!$ possible initial orderings of the list. Show that after $k$ of the compare-and-swap operations have been applied, at most $2^k$ of the possible initial orderings will have been sorted into the correct order. Conclude that $\Omega(n \log n)$ compare-and-swap operations are required to sort all possible initial orderings into the correct order.
The compare-and-swap(j,k)
operation is defined as:
compares the list entries numbered $j$ and $k$, and swaps them if they are out of order
Using an inductive argument, I understand that $k$ applications of the compare-and-swap operation sorts at most $2^k$ of the possible initial orderings into the correct order. However, I have trouble drawing the final conclusion from this, specifically that $\Omega(n \log n)$ compare-and-swap operations are required to sort all possible initial orderings.
$n \log n$ steps will sort at most $2^{n \log n}=\left(2^{\log n} \right)^n=n^n \gt n!$ of the possible orderings. So $n \log n$ steps might be enough to sort all possible orderings but I don't see why we need at least this many steps (which is what I think $\Omega(\cdot)$ means)? To me there seems to be a gap between $n^n$ and $n!$ and it's not obvious why there can't be an algorithm which solves the task by covering more than (or exactly) $n!$ but less than $n^n$ orderings?