Quicksort, mergesort, and heapsort are examples of general-purpose sorting algorithms.

They have O(NlogN) time complexity.

Do you think you can design a faster algorithm?

These algorithms are based on comparisons and generate a decision tree

whose leaves represent all possible arrangements of the elements of the input.

The height of the tree equals the max number of comparisons needed to produce one of these arrangements.

An input of N items produces N! permutations->the decision tree must have N! leaves

A tree of height h has at most 2^h leaves

Then, 2^h>=N!

Taking logs, h>=log(N!)

Using Stirling& #39;s approximation, h>=NlogN

The minimum number of comparisons has a lower bound of order NlogN

So, no. You cannot do better than NlogN.

However, in some cases, you can sort in O(n).

Integers, for example.

Have a look at this for more info:

http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap09.htm

Algorithms">https://staff.ustc.edu.cn/~csli/gra... are very math-heavy. I& #39;ll post more of this content if you like it

If you enjoyed this thread, please like and retweet the first tweet.

Thanks! https://twitter.com/CodingLanguages/status/1300801049935204354?s=20">https://twitter.com/CodingLan...