When I studied comparison sorts (like merge sort, quick sort) I always have a question in mind how further can we optimize the algorithm to decrease the time complexity? The answer to this question is that the lower bound of any comparison sort cannot be less than O(N log N) for the worst case.

Now the question arises how can we come to such a conclusion.

Comparison between two elements(let's take x, y) results in one of the 2 results

• x>y (> and >= are consider same)

• x<y(< and <= are consider same)

Now since there can be 2 results we can represent the same using a binary tree. Let's take an example of 3 elements insertion sort

This tree is called the Decision tree. Here we show all the possible outcomes .

Now we generalize this case :

• We have n elements
• There can be n! permutations (there can be n! results such as [x,y,z],[x,z,y],[y,x,z]... and so on)
• Binary tree of height h can have max 2^h leaves (l)
• n!<leaves (l) (since all the possible outputs are shown in the leaves in the tree)

n! <= l and l <=2^h

=>n! <= 2^h

=>h >= log(n!)

n!=O(n^n)

n!=ω(2^n)

log(n!)=O(n log n)

=>h=log(n log n)

Hence it proved that the lower bound for comparison sort is O(N log N).

Thank you.