Here is a lower bound proof for the comparison-based sorting problem:
- Any comparison-based sorting algorithm can be considered to work by putting elements into their final positions one by one (Take the last time one element is put into its final position.).
- To put the element $e$ which is the $i$-th one being put into its final position, the algorithms should know the relative ordering between $e$ and the first $n-1$ elements that are already put into their final positions. This costs at least $\Omega(\lg i)$ comparisons.
- Therefore, the total number of comparisons is at least $$\sum_{i=1}^{n-1} \lg i = \Omega(n \lg n).$$
Is this a reasonable proof? (I am quite confused about the second step.) If so, how to formalize it more rigorously?