Lower Bounds for Comparison based Sort

• In a comparison sort, we use only comparisons between elements to gain order information about an input sequence a₁, a₂, ...., a_n.
• For given 2 elements a_i and a_j , we perform one of the tests a_i < a_j , a_i ≤ a_j , a_i = a_j , a_i ≥ a_j, a_i > a_j to determine their relative order.
• Comparison sorts can be viewed abstractly in terms of decision trees.

The execution of the sorting algorithm corresponds to tracing a path from the root of the decision tree to a leaf. At each internal node, a comparison ai <= aj is made. The left subtree then dictates subsequent comparisons for ai <= aj, and the right subtree dictates subsequent comparisons for ai > aj. When we come to a leaf, the sorting algorithm has established the ordering. So we can say following about the decision tree. 

• Each of the n! permutations on n elements must appear as one of the leaves of the decision tree for the sorting algorithm to sort properly. 
• Let x be the maximum number of comparisons in a sorting algorithm. The maximum height of the decision tree would be x. A tree with maximum height x has at most 2^x leaves.

After combining the above two facts, we get following relation. 

n! ≤ 2^x
 Taking Log on both sides.
      log2(n!)  ≤ x
 Since log2(n!) = Θ(n log n), we can say
x = Ω(n log 2n)