Find the least number of comparisons needed to sort (order) five elements and devise an algorithm that sorts these elements using this number of comparisons.
Solution: There are 5! = 120 possible outcomes. Therefore a binary tree for the sorting procedure will have at least 7 levels. Indeed, $2^h$ ≥ 120 implies $h $ ≥ 7. But 7 comparisons is not enough. The least number of comparisons needed to sort (order) five elements is 8.
Here is my actual question: I did find an algorithm that does it in 8 comparison but how can I prove that it can't be done in 7 comparisons?