Write down the essence of the proof that a comparison-based sort is (n log n) where n is the number of elements to sort. I am not asking for the algebraic tricks based on Stirling's approximation. In fact, I want to see no algebra at all. I want to know if you understand the fundamental idea of the proof; the reasons that lead to using Sirling's approximation.

Proof We have n! permutations of n elements, So we must have at least n! leaves. (We may have more if the sort is not optimal.) o A binary tree of height h has at most 2h leaves. o Therefore, we need the smallest h such that n! 2h n!2h log(n!) S h B y Stirling s approximation n -Van (2) n (1 + (j) n log ( ) + log V2tn