Shortest possible depth of a leaf in decision tree (comparison sorting algorithm)

Question

What is the shortest possible depth of a leaf in decision tree refering to comparison sorting algorithm ?

Does it change depending on the alogrithm?

Answer 1

The absolute best case happens when we just check every element and see that the data's already sorted.

This will result in n-1 comparisons and thus the leaf will have a depth of n-1.

Practically, this happens for insertion sort (which isn't all that good otherwise though).

Does it change depending on the algorithm?

Absolutely. The best case of an algorithm is a good indicator - the shortest depth for one with O(n log n) best case would be longer than the shortest depth for one with O(n) best case.

Answer 2

To see this consider a graph of n nodes, each node i representing A[i]. Draw a (directed) edge from i to j if we compare A[i] with A[j] on the path from root to . Note that for k < n−1, this graph on {1, . . . , n} will not be connected. Hence we have two components C1 and C2 and we know nothing about the relative order of array elements indexed by C1 against elements indexed by C2. therefore there cannot be a single permutation π that sorts all inputs passing these k tests - so π() is wrong for some arrays which lead to leaf