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 1 , a 2 , ...., 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 l...
