The lower bound of comparisons in a comparison-based sorting algorithm is $ \log_2 n!=Θ(n\log n)$ . Yet there can be less comparisons needed in an algorithm. If you take a sorted array, it will take $ n-1 = O(n)$ comparisons (with insertion sort) to sort the array — comparing every adjacent pair of numbers. I don’t understand then how is $ \log_2 n!=Θ(n\log n)$ the lower bound.

I also don’t understand the corresponding trees to the sorting-based algorithms: each leaf in the tree corresponds to one of the permutations of the $ n$ numbers. If the minimum number of comparisons needed is $ \log_2 n!$ then the depth of every leaf should be at least $ \log_2 n!$ , yet I saw that it’s possible for a leaf to be with depth of $ O(n)$ .

Can there be leaves with depth even smaller than $ n-1$ ?