list of distinct numbers (we can assume this because this is a worst-case analysis), there are factorial permutations exactly one of which is the list in sorted order. The sort algorithm must gain enough information from the comparisons to identify the correct permutation. If the algorithm always completes after at most steps, it cannot distinguish more than cases because the keys are distinct and each comparison has only two possible outcomes. Therefore, , or equivalently By looking at the first factors of , we obtain This provides the lower-bound part of the claim. A more precise bound can be given via Stirling's approximation. An upper bound of the same form, with the same leading term as the bound obtained from Stirling's approximation, follows from the existence of the algorithms that attain this bound in the worst case, like merge sort. The above argument provides an absolute, rather than only asymptotic lower bound on the number of comparisons, namely comparisons. This lower bound is fairly good (it can be approached within a linear tolerance by a simple merge sort), but it is known to be inexact. For example, , but the minimal number of comparisons to sort 13 elements has been proved to be 34. Determining the exact number of comparisons needed to sort a given number of entries is a computationally hard problem even for small n, and no simple formula for the solution is known. For some of the few concrete values that have been computed, see . Lower bound for the average number of comparisons A similar bound applies to the average number of comparisons. Assuming that all keys are distinct, i.e. every comparison will give either a>b or a<b, and the input is a random permutation, chosen uniformly from the set of all possible permutations of n elements, it is impossible to determine which order the input is in with fewer than comparisons on average. This can be most easily seen using concepts from information theory. The Shannon entropy of such a random permutation is bits. Since a comparison can give only two results, the maximum amount of information it provides is 1 bit. Therefore, after k comparisons the remaining entropy of the permutation, given the results of those comparisons, is at least bits on average. To perform the sort, complete information is needed, so the remaining entropy must be 0. It follows that k must be