What is the smallest possible depth of a leaf in a decision tree for a comparison sort?
当数组已经排序好，是n-1.
Obtain asymptotically tight bounds on lg(n!) without using Stirling's approximation. Instead, evaluate the summation 
using techniques from Section A.2.
Show that there is no comparison sort whose running time is linear for at least half of the n! inputs of length n. What about a fraction of 1/n of the inputs of length n? What about a fraction 1/2^n?
n!/2, n!/n, n!/(2^n) are smaller than 2^n only when n is small.
You are given a sequence of n elements to sort. The input sequence consists of n/k subsequences, each containing k elements. The elements in a given subsequence are all smaller than the elements in the succeeding subsequence and larger than the elements in the preceding subsequence. Thus, all that is needed to sort the whole sequence of length n is to sort the k elements in each of the n/k subsequences. Show an Ω(n lg k) lower bound on the number of comparisons needed to solve this variant of the sorting problem. (Hint: It is not rigorous to simply combine the lower bounds for the individual subsequences.)
Follow @louis1992 on github to help finish this task.