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.