Sorting : proof for lower bound of Sorting [closed]

Question

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.

Thanks :)

Answer 1

Any comparison-based algorithm corresponds to a decision tree. To construct the decision tree, just follow the workings of the algorithm. Each time the algorithm makes a comparison, consider both outcomes. Since the algorithm only has access to the array to be sorted via these comparisons, you don't have to keep any kind of array in mind. Finally, when the algorithm is done, it knows the correct order of the elements in the array. That's exactly the decision tree model.

Each root-to-leaf path in the decision tree corresponds to one possible computation path of the algorithm. The height of the tree is thus the length of the longest computation path, which is a lower bound on the worst-case running time of the algorithm.