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?