# Lower bound for comparison based sorting algorithms

• Difficulty Level : Easy
• Last Updated : 06 Jul, 2021

The problem of sorting can be viewed as following.

Input: A sequence of n numbers <a1, a2, . . . , an>.
Output: A permutation (reordering) <a1, a2, . . . , an> of the input sequence such that a1 <= a2 ….. <= a’n

A sorting algorithm is comparison based if it uses comparison operators to find the order between two numbers.  Comparison sorts can be viewed abstractly in terms of decision trees. A decision tree is a full binary tree that represents the comparisons between elements that are performed by a particular sorting algorithm operating on an input of a given size. 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.

1) 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.

2) 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!)  = Θ(nLogn),  we can say
x = Ω(nLog2n)```

Therefore, any comparison based sorting algorithm must make at least nLog2n comparisons to sort the input array, and Heapsort and merge sort are asymptotically optimal comparison sorts.

My Personal Notes arrow_drop_up