I have read the proof of lower bound of Sorting Algorithm that use comparison to know input is NlogN. In this paper, the author use decision tree for this proof. Everything on this proof I have understand well ( height of decision tree, the inequality is used...) but one thing :
lower bound on height equivalent to lower bound on sorting.
I have thought so much, but I still cannot understand why. In sorting algorithm, in "normal sense", I feel that there are many ways for sorting (although just use comparison), and I don't see connection between decision tree(to compare n items) to the sorting problem.
Anyone here please give me an idea for this statement.