# Minimum depth of a leaf in a tree that corresponds to a comparison-based sorting algorithm

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$$?