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 log2(n!) − k bits on average. To perform the sort, complete information is needed, so the remaining entropy must be 0.