Lower bounds on comparison is n logn

Problem: A = {a, b, c, d, ... n elements}
find a permutation of the element of A, {a', b', c', ... } where a' <  b' < c' so on and so forth.

how many comparisons we need to make at least? the answer will be the lower bound of the comparison-based sort.

Analysis:
We can think of a binary tree, each comparing two elements of A. At the leaf, we will reach one of the permutations.

At the leaf we will have all n! permutations of elements of A. Lets height of the tree is h. So, h will minimum number of comparisions we need to sort A.

for binary trees,
2 ^ h >= number of leaves
2 ^ h >= n!
h >= log n!
h >= log ((n/e) ^ n) #sterling formulat
h >= n log(n/e)
h ~ O(n logn)

A sample decision tree for 3 elements can be seen in the following figure.