2

I was looking into binary, binomial and Fibonacci heap sort and I found out that takes O(n log n) time to sort. It would be great if someone can give me a reason as to why it is so.

Somit
  • 51
  • 3
  • 1
    Last I knew (which was a long time ago) this was still an unproven theorem. – john Nov 28 '20 at 21:09
  • Simple reason: Nobody has come up with a sorting algorithm that beats that. There is not currently, as far as I know, a law or whatnot that states that this is the theoretical minimum, it's just that nobody has managed to improve on it. – Lasse V. Karlsen Nov 28 '20 at 21:09
  • 1
    https://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list – user14644949 Nov 28 '20 at 21:14

1 Answers1

4

A list of n elements has n! permutations. One of these permutations is the correctly sorted one. A single comparison between two elements conveys only 1 bit of information and therefore can't possibly do any better than cutting the search space in half. So a lower bound on the number of comparisons needed to distinguish the correctly sorted permutation from all other permutations is log2(n!) ∈ O(n log n).

Note that log2(n!) really is just a lower bound - it doesn't mean that it is actually possible to sort n number with exactly ceiling(log2(n!)) comparisons. In fact, there are permutations for which you need a few more comparisons. But this doesn't matter if we are just interested in the asymptotic behaviour.

So you see that if we don't restrict ourselves to comparison-based sorting algorithms, the lower bound doesn't hold. (See e.g. bucket sort or radix sort.)

Mo B.
  • 5,307
  • 3
  • 25
  • 42