at least on average. The lower bound derived via information theory is phrased as 'information-theoretic lower bound'. Information-theoretic lower bound is correct but is not necessarily the strongest lower bound. And in some cases, the information-theoretic lower bound of a problem may even be far from the true lower bound. For example, the information-theoretic lower bound of selection is whereas comparisons are needed by an adversarial argument. The interplay between information-theoretic lower bound and the true lower bound are much like a real-valued function lower-bounding an integer function. However, this is not exactly correct when the average case is considered. To unearth what happens while analyzing the average case, the key is that what does 'average' refer to? Averaging over what? With some knowledge of information theory, the information-theoretic lower bound averages over the set of all permutations as a whole. But any computer algorithms (under what are believed currently) must treat each permutation as an individual instance of the problem. Hence, the average lower bound we're searching for is averaged over all individual cases. To search for the lower bound relating to the non-achievability of computers, we adopt the Decision tree model. Let's rephrase a bit of what our objective is. In the Decision tree model, the lower bound to be shown is the lower bound of the average length of root-to-leaf paths of an -leaf binary tree (in which each leaf corresponds to a permutation). It would be convinced to say that a balanced full binary tree achieves the minimum of the average length. With some careful calculations, for a balanced full binary tree with leaves, the average length of root-to-leaf paths is given by For example, for , the information-theoretic lower bound for the average case is approximately 2.58, while the average lower bound derived via Decision tree model is 8/3, approximately 2.67. In the case that multiple items may have the same key, there is no obvious statistical interpretation for the term "average case", so an argument like the above cannot be applied without making specific assumptions about the distribution of keys. n log n maximum number of comparisons for array-size in format 2^k Can easy compute for real algorithm sorted-list-merging (array are sorted n-blocks with size 1, merge to 1-1 to 2, merge 2-2 to 4...). (1) = = = = = = = = (2) = = = = // max 1 compares (size1+size2-1),