Sorting n weight disks with decision tree

Question

I was refreshing some old tests about sorting algorithms, there was a question as follow:

Question: we have n weight disks with different weights and we want to sort them pair by pair, How many times we have to weight in worst case (maximum comparisons) to sort the whole disks?

the answer was $ \lceil \log n! \rceil $.

My issue is that I could not get to the answer and could anyone elaborate on how the answer is working?

Also one of the options was $ \lceil n\log n \rceil $, and as we know, the order of $\log n!$ and $n\log n$ are same, So why shouldn't the ceilings be equal too?

and How does having an ordered and distinct set of size n, matter in decision tree?

Answer 1

I suspect that the question is looking for a non necessarily tight lower bound to the number of comparisons needed.

The decision tree needs to be able to return the correct sorted sequence no matter what the initial permutation of the elements is. Therefore, it must have at least $n!$ leaves (one for each output permutation). Each internal vertex in the decision tree represents a comparison has has $2$ children. This means that the height of the tree must be at least $\log_2 n!$. Since the height must be an integer, you can take the ceiling.

However no algorithm can attain this number of comparisons in the worst case for all values of $n$ (notice that the intended answer does not use the asymptotic notation). Here you can find the number of comparisons needed to sort $n$ elements for some small values of $n$. For $n=15$, $\lceil \log 15! \rceil = 41$ but $42$ comparisons are needed.

To answer your second question, $\lceil n \log n \rceil$ is incorrect since it not a valid lower bound. For example, for $n=2$, $2 \log 2 = 2$ but $1$ comparison is sufficient. You are right in saying that $O(\log n!) = O(n \log n)$ but notice how the answers are not using the big-Oh notation.

Finally, you need the discs to be linearly ordered otherwise it doesn't make sense to compare them. Moreover the fact that the input elements are distinct allows you to consider a decision tree where the outcome of each comparison is binary and is either "greater than" or "smaller than".