You can see from the decision tree below, that it is possible to sort any array of 3 numbers within 3 comparisons. Each internal node here represents one comparison (for example 1:2 is comparing the elements initially at index 1 and index 2). If we hit a leaf node, then we have narrowed the possibilities down to only one permutation of the original list, so we have our sorted order. Since all 6 possible permutations of the array appear in this decision tree of height 3 , we can sort any 3 element array in 3 comparisons. Prove that for any comparison-based sorting algorithm used on an array of n elements, if n>4, then for most permutations the array can't be sorted within n comparisons (that is, more than half of the permutations are not in the first n levels of the decision tree). Hint: What is the maximum number of leaves a decision tree of height h=n can have? How many permutations does an array of n elements have? Can you prove by induction that it's not possible for at least half of them to fit into the leaves of said tree