The leaf of the decision tree always has depth n-1.
What is the smallest possible depth of a leaf in a decision tree for a sorting algorithm?
The shortest possible depth is n-1. To see this, observe that if we have a root leaf path with k comparisons, we cannot sure that the permutation at the leaf l is the correct one.
Proof:
To see this consider a graph of n nodes, each node representing A[i]. Draw an edge from I to j if we compare A[i] with A[j] on the path from the root to l.
Hence we have two components C1 and C2, and we know nothing about the relative order of array element indexed C1 and C2 against elements indexed by C2. Therefore there cannot be a single permutation that sorts all inputs passing these k tests.
Does it change depends on the algorithms?
It will change according to algorithms. Here is the best case of an algorithm and treated as a good indicator. The shortest depth for one with complexity O (n logn) with the best case would be larger than the shortest depth for the ones with the complexity O(n) of the best case.
Note:
The best case only happens when every element of the tree is already sorted.