Just a little nitpicking, the
decision tree based proof is a
lower bound proof, thus the proper notation above should be
Ω(n log n). To prove that the *problem* of sorting is O(n log n), we can just look at one
algortihm such as
merge sort, and show that it is O(n log n) in the worst case.
Proving the lower bound is more involved, as shown in the writeup above. As a consequence of knowing that the problem of sorting is O(n log n) and Ω(n log n), we know that the problem of sorting is Θ(n log n).
Again, as above a caveat. The proof is only for comparison-based sorting. Bin sort (also known as Bucket Sort) is Θ(n), but you need to reserve space for all possible keys.